Problem

You are given a license key represented as a string s that consists of only alphanumeric characters and dashes. The string is separated into n + 1 groups by n dashes. You are also given an integer k.

We want to reformat the string s such that each group contains exactly k characters, except for the first group, which could be shorter than k but still must contain at least one character. Furthermore, there must be a dash inserted between two groups, and you should convert all lowercase letters to uppercase.

Return the reformatted license key.

Examples

Example 1:

Input: s = “5F3Z-2e-9-w”, k = 4 Output: “5F3Z-2E9W” Explanation: The string s has been split into two parts, each part has 4 characters. Note that the two extra dashes are not needed and can be removed.

Example 2:

Input: s = “2-5g-3-J”, k = 2 Output: “2-5G-3J” Explanation: The string s has been split into three parts, each part has 2 characters except the first part as it could be shorter as mentioned above.

Solution

Method 1 – Reverse and Greedy Grouping

Intuition

The main idea is to ignore dashes, convert all letters to uppercase, and then group the characters from the end in chunks of size k. This way, the first group can be shorter, and the rest are exactly k in length.

Approach

  1. Remove all dashes and convert all letters to uppercase.
  2. Start from the end of the string and collect groups of size k.
  3. Join the groups with dashes, reversing at the end to restore the correct order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public String licenseKeyFormatting(String s, int k) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c != '-') sb.append(Character.toUpperCase(c));
        }
        StringBuilder ans = new StringBuilder();
        int cnt = 0;
        for (int i = sb.length() - 1; i >= 0; --i) {
            if (cnt == k) {
                ans.append('-');
                cnt = 0;
            }
            ans.append(sb.charAt(i));
            cnt++;
        }
        return ans.reverse().toString();
    }
}
1
2
3
4
5
6
7

class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        s = s.replace('-', '').upper()
        ans: list[str] = []
        for i in range(len(s), 0, -k):
            ans.append(s[max(0, i - k):i])
        return '-'.join(ans[::-1])

Complexity

  • ⏰ Time complexity: O(n) — Each character is processed a constant number of times.
  • 🧺 Space complexity: O(n) — For the cleaned string and the answer.

Method 2 – Forward Grouping with Modulo

Intuition

By removing dashes and uppercasing, we can process the string from the start, placing a dash before every group except the first, using the modulo of the current index to determine when to insert a dash.

Approach

  1. Remove all dashes and convert to uppercase.
  2. Calculate the length of the first group: len(s) % k (unless it’s zero, then it’s k).
  3. Build the result by adding the first group, then every next group of size k with a dash before each.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public String licenseKeyFormatting(String s, int k) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c != '-') sb.append(Character.toUpperCase(c));
        }
        String str = sb.toString();
        StringBuilder ans = new StringBuilder();
        int first = str.length() % k;
        if (first == 0 && str.length() > 0) first = k;
        ans.append(str.substring(0, first));
        for (int i = first; i < str.length(); i += k) {
            if (ans.length() > 0) ans.append('-');
            ans.append(str.substring(i, i + k));
        }
        return ans.toString();
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        s = s.replace('-', '').upper()
        first = len(s) % k or k
        ans = s[:first]
        for i in range(first, len(s), k):
            ans += '-' + s[i:i+k]
        return ans

Complexity

  • ⏰ Time complexity: O(n) — Each character is processed a constant number of times.
  • 🧺 Space complexity: O(n) — For the cleaned string and the answer.