License Key Formatting

Difficulty: Easy | Acceptance: 46.00% | Paid: No Topics: String

You are given a license key represented as a string s that consists of 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 groups, and you should convert all lowercase letters to uppercase.

Return the reformatted license key.

• Examples
• Constraints
• Approach 1: Reverse Iteration
• Approach 2: Clean and Slice

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.

Constraints

- 1 <= s.length <= 10^5
- s consists of English letters, digits, and dashes '-'.
- 1 <= k <= 10^4

Approach 1: Reverse Iteration

Intuition It is easiest to build the string from the end because the first group is the only one allowed to have a length different from k. By iterating backwards, we can simply insert a dash after every k characters.

Steps

• Initialize an empty list/array to store characters and a counter for the current group size.
• Iterate through the string s from the last character to the first.
• If the character is a dash, skip it.
• Append the uppercase version of the character to the result list.
• Increment the counter. If the counter reaches k and we are not at the start of the original string, append a dash to the result and reset the counter.
• Reverse the result list and join it into a string to return.

class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        res = []
        count = 0
        for i in range(len(s) - 1, -1, -1):
            if s[i] == '-':
                continue
            res.append(s[i].upper())
            count += 1
            if count == k and i != 0:
                res.append('-')
                count = 0
        return ''.join(reversed(res))

Complexity

• Time: O(N), where N is the length of the string. We traverse the string once.
• Space: O(N) to store the result.
• Notes: This approach is efficient because it handles the “first group shorter” rule naturally by building from the end.

Approach 2: Clean and Slice

Intuition First, remove all dashes and convert the string to uppercase. Then, calculate the length of the first group based on the total length modulo k. Finally, construct the new string by slicing the cleaned string and inserting dashes.

Steps

• Iterate through s to build a new string containing only alphanumeric characters in uppercase.
• Calculate the length of the first group: len(cleaned) % k. If the remainder is 0, the first group length is k.
• Initialize the result with the first group.
• Iterate through the rest of the cleaned string in chunks of size k, appending a dash followed by the chunk to the result.

class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        clean = []
        for ch in s:
            if ch != '-':
                clean.append(ch.upper())
        n = len(clean)
        if n == 0:
            return ""
        first_len = n % k
        if first_len == 0:
            first_len = k
        res = []
        for i in range(first_len):
            res.append(clean[i])
        i = first_len
        while i < n:
            res.append('-')
            for j in range(k):
                res.append(clean[i])
                i += 1
        return "".join(res)

Complexity

• Time: O(N), where N is the length of the string. We pass through the string to clean it and once more to build the result.
• Space: O(N) to store the cleaned string and the result.
• Notes: This approach is intuitive but requires two passes over the data (or one pass to clean and one to build).