License Key Formatting

Easy

#0469Time: O(N), where N is the length of the input string `s`. The `replace` and `toUpperCase` operations take O(N) time. The loop to build the final string also iterates through the cleaned string once, taking O(N) time.Space: O(N), where N is the length of the input string. An intermediate string of length up to N is created for the cleaned data. The `StringBuilder` also uses space up to O(N) for the result.

Data structures

String

Prompt

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.

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.

Constraints:

1 <= s.length <= 10⁵
s consists of English letters, digits, and dashes '-'.
1 <= k <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

This approach first cleans the input string by removing all dashes and converting letters to uppercase. Then, it rebuilds the formatted string from this cleaned version by inserting dashes at the appropriate positions. The main challenge is correctly calculating the length of the first group, which might be shorter than k.

Algorithm

Create a new string cleanedS by removing all dashes from s and converting it to uppercase using replace() and toUpperCase() methods.
If cleanedS is empty, return an empty string.
Calculate the length of the first group. This will be cleanedS.length() % k. If the remainder is 0 (and the string is not empty), it means all groups are of size k, so the first group's length is k.
Initialize a StringBuilder to build the result.
Append the first group of characters from cleanedS to the StringBuilder.
Iterate through the rest of cleanedS with a step of k.
In each iteration, append a dash - followed by the next k characters to the StringBuilder.
Return the final string from the StringBuilder.

Walkthrough

The core idea is to separate the problem into two distinct steps: data preparation and formatting.

Preparation: We first create a new string that contains only the alphanumeric characters from the input string, all converted to uppercase. This can be done easily using built-in string methods like replace("-", "") and toUpperCase().
Formatting: Once we have the clean string of length L, we can determine the length of the first group. The length of all subsequent groups is k. The length of the first group will be L % k. If L % k is 0, it means all groups, including the first, will have k characters. We then use a StringBuilder to construct the final result. We first append the first group. After that, we loop through the rest of the cleaned string, appending a dash and then k characters for each subsequent group until the entire cleaned string is processed.

1public class Solution {2    public String licenseKeyFormatting(String s, int k) {3        // 1. Clean the string: remove dashes and convert to uppercase.4        String cleanedS = s.replace("-", "").toUpperCase();5        int len = cleanedS.length();6        if (len == 0) {7            return "";8        }9 10        StringBuilder result = new StringBuilder();11 12        // 2. Calculate the length of the first group.13        int firstGroupLen = len % k;14        if (firstGroupLen == 0) {15            firstGroupLen = k;16        }17 18        // 3. Append the first group.19        result.append(cleanedS.substring(0, firstGroupLen));20 21        // 4. Append the rest of the groups.22        for (int i = firstGroupLen; i < len; i += k) {23            result.append("-");24            result.append(cleanedS.substring(i, i + k));25        }26 27        return result.toString();28    }29}

Complexity

Time

O(N), where N is the length of the input string `s`. The `replace` and `toUpperCase` operations take O(N) time. The loop to build the final string also iterates through the cleaned string once, taking O(N) time.

Space

O(N), where N is the length of the input string. An intermediate string of length up to N is created for the cleaned data. The `StringBuilder` also uses space up to O(N) for the result.

Trade-offs

Pros

The logic is straightforward and easy to understand as it separates the cleaning and formatting steps.
Makes good use of built-in string manipulation functions.

Cons

Requires creating an intermediate string to hold the cleaned data, which uses extra memory (O(N)).
Effectively involves multiple passes over the data (one to clean, another to build the result), which can be less performant due to memory allocations and copying.

This is a more optimized approach that processes the input string in a single pass from right to left. By building the result string backwards, it naturally handles the condition that the first group can be shorter than k without needing to calculate its length beforehand.

Algorithm

Initialize an empty StringBuilder to store the result and a character counter count to 0.
Iterate through the input string s from right to left (from the last character to the first).
For each character c:
- If c is a dash (-), ignore it and continue to the next character.
- If c is an alphanumeric character:
  - First, check if count is equal to k. If it is, it means a group is complete, so we append a dash - to the StringBuilder and reset count to 0.
  - Append the uppercase version of c to the StringBuilder.
  - Increment count.
After the loop finishes, the StringBuilder contains the formatted string but in reverse order.
Reverse the StringBuilder and return its string representation.

Walkthrough

The key insight for this approach is that all groups except the first one must have exactly k characters. This rigid structure from the end of the string suggests that processing it from right to left would be more natural.

We use a StringBuilder for efficient string construction. We iterate backwards from the end of the input string s. We maintain a counter for the number of alphanumeric characters we've added to the current group. When we encounter an alphanumeric character, we check if our counter has reached k. If it has, we know we've just finished a group, so we append a dash to our StringBuilder before adding the new character. Then, we append the uppercase version of the character and increment our counter.

Since we processed the original string from right to left, our StringBuilder will hold the final, formatted string in reverse order. The final step is to simply call the reverse() method on the StringBuilder and convert it to a string.

1public class Solution {2    public String licenseKeyFormatting(String s, int k) {3        StringBuilder result = new StringBuilder();4        int count = 0;5 6        // Iterate from the end of the string to the beginning.7        for (int i = s.length() - 1; i >= 0; i--) {8            char c = s.charAt(i);9            if (c == '-') {10                continue;11            }12 13            // If we have a full group, append a dash first.14            if (count == k) {15                result.append('-');16                count = 0;17            }18 19            result.append(Character.toUpperCase(c));20            count++;21        }22 23        // The result is built in reverse, so we need to reverse it at the end.24        return result.reverse().toString();25    }26}

Complexity

Time

O(N), where N is the length of the input string `s`. We iterate through the string once. The final `reverse()` operation on the `StringBuilder` also takes time proportional to its length, which is at most O(N).

Space

O(N), where N is the length of the input string. This space is used by the `StringBuilder` to construct the result. This is optimal as the output string itself can be of length O(N).

Trade-offs

Pros

Highly efficient as it processes the string in a single pass.
Avoids creating an intermediate string, which reduces memory overhead and improves performance.
Elegantly handles the variable-length first group without any special calculations.

Cons

The logic of building the string in reverse and then reversing it at the end might be slightly less intuitive at first glance compared to a forward-building approach.

Solutions

Solution

1class Solution {2public3  String licenseKeyFormatting(String s, int k) {4    s = s.replace("-", "").toUpperCase();5    StringBuilder sb = new StringBuilder();6    int t = 0;7    int cnt = s.length() % k;8    if (cnt == 0) {9      cnt = k;10    }11    for (int i = 0; i < s.length(); ++i) {12      sb.append(s.charAt(i));13      ++t;14      if (t == cnt) {15        t = 0;16        cnt = k;17        if (i != s.length() - 1) {18          sb.append('-');19        }20      }21    }22    return sb.toString();23  }24}

1class Solution {2public:3  string licenseKeyFormatting(string s, int k) {4    string ss = "";5    for (char c : s) {6      if (c == '-')7        continue;8      if ('a' <= c && c <= 'z')9        c += 'A' - 'a';10      ss += c;11    }12    int cnt = ss.size() % k;13    if (cnt == 0)14      cnt = k;15    int t = 0;16    string res = "";17    for (int i = 0; i < ss.size(); ++i) {18      res += ss[i];19      ++t;20      if (t == cnt) {21        t = 0;22        cnt = k;23        if (i != ss.size() - 1)24          res += '-';25      }26    }27    return res;28  }29};

1class Solution:2    def licenseKeyFormatting(self, s: str, k: int) -> str: s = s . replace('-', ''). upper() res = [] cnt = (len(s) % k) or k t = 0 for i, c in enumerate(s): res . append(c) t += 1 if t == cnt: t = 0 cnt = k if i != len(s) - 1: res . append('-') return '' . join(res)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem