LeetCode 482 - License Key Formatting

LeetCode Problem 482

Difficulty: 🟢 Easy
Topics: String

Solution

Problem Understanding

The problem gives us a string s that represents a license key. The string contains uppercase letters, lowercase letters, digits, and dashes. The existing dashes are only separators and do not necessarily represent the correct final grouping.

We must reformat the string according to two rules:

1. Every group after formatting must contain exactly k characters, except the first group.
2. The first group may contain fewer than k characters, but it must contain at least one character.

In addition, all alphabetic characters must be converted to uppercase, and groups must be separated by single dashes.

For example, suppose the input is:

"5F3Z-2e-9-w"

and k = 4.

If we remove all dashes first, we get:

"5F3Z2e9w"

After converting to uppercase:

"5F3Z2E9W"

Now we group from left to right into chunks of size 4:

"5F3Z-2E9W"

That becomes the final answer.

The constraints are important:

• s.length can be as large as 10^5
• k can be as large as 10^4

This immediately tells us that we need a linear-time solution. Any approach that repeatedly inserts characters into the front of a string or rebuilds strings inefficiently could become too slow.

There are several edge cases that can cause mistakes in naive implementations:

• Strings with many dashes, such as "---a---"
• Strings where the total number of characters is exactly divisible by k
• Strings where the first group should contain fewer than k characters
• Lowercase letters that must be converted correctly
• Very small values of k, such as 1
• Inputs that already appear formatted correctly

The problem guarantees that there is at least one alphanumeric character somewhere in the string, so the final result will always contain at least one group.

Approaches

Brute Force Approach

A straightforward approach is to first remove all dashes and convert the remaining characters to uppercase. Then we repeatedly build groups from the front of the string.

One naive implementation would repeatedly slice substrings and concatenate them into the result string using normal string addition. Since strings are immutable in many languages, repeated concatenation can become expensive because every append may create a new copy of the string.

For example:

result = result + "-" + next_group

If this operation is repeated many times on large inputs, the total runtime can degrade toward quadratic complexity.

This approach is correct because it explicitly reconstructs the formatted string according to the grouping rules. However, it is inefficient for large inputs.

Optimal Approach

The key insight is that the formatting becomes much easier if we process the characters from right to left.

Every group except possibly the first must contain exactly k characters. That means if we build the string backward, we can simply insert a dash after every k characters.

The process becomes:

1. Traverse the original string from the end.
2. Ignore dashes.
3. Convert letters to uppercase.
4. Append characters into a result buffer.
5. After every k characters, append a dash.
6. Reverse the final result at the end.

Using a mutable list or string builder avoids expensive repeated string concatenation, giving us linear performance.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeated string concatenation can repeatedly copy data
Optimal	O(n)	O(n)	Single pass with efficient buffer construction

Algorithm Walkthrough

1. Create an empty result buffer that will store characters in reverse order.
2. Initialize a counter to track how many characters have been added to the current group.
3. Traverse the string from right to left. Processing backward is useful because all groups except the first must have exactly k characters. Building from the end naturally enforces this rule.
4. For each character:

• If the character is a dash, skip it because original dashes are irrelevant.

• Otherwise:

• Convert the character to uppercase.

• Append it to the result buffer.

• Increment the group counter.

5. Whenever the group counter reaches k, append a dash to the result buffer and reset the counter to zero. This creates properly sized groups while processing backward.
6. After traversal finishes, there may be an extra dash at the end of the reversed buffer. Remove it if necessary.
7. Reverse the buffer and join it into the final string.

Why it works

The algorithm maintains the invariant that every completed group in the reversed buffer contains exactly k characters. Since we process from right to left, the grouping constraint is naturally satisfied for all groups except possibly the first. After reversing the buffer, the groups appear in the correct left-to-right order, and the first group automatically contains the remaining characters, which may be fewer than k.

Python Solution

class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        result = []
        group_size = 0

        for index in range(len(s) - 1, -1, -1):
            char = s[index]

            if char == "-":
                continue

            result.append(char.upper())
            group_size += 1

            if group_size == k:
                result.append("-")
                group_size = 0

        if result and result[-1] == "-":
            result.pop()

        return "".join(reversed(result))

The implementation uses a list named result as a mutable buffer because appending to a list is efficient in Python. Building strings directly with repeated concatenation would be slower.

The loop iterates backward through the input string. This makes it easy to create groups of exactly k characters because we can simply insert a dash every time the counter reaches k.

Each non-dash character is converted to uppercase immediately before being appended.

After processing all characters, the buffer may end with an unnecessary dash. This happens when the total number of characters is divisible by k. The conditional pop() removes it safely.

Finally, the buffer is reversed and joined into the correctly formatted string.

Go Solution

func licenseKeyFormatting(s string, k int) string {
    result := make([]byte, 0)
    groupSize := 0

    for i := len(s) - 1; i >= 0; i-- {
        ch := s[i]

        if ch == '-' {
            continue
        }

        if ch >= 'a' && ch <= 'z' {
            ch = ch - 'a' + 'A'
        }

        result = append(result, ch)
        groupSize++

        if groupSize == k {
            result = append(result, '-')
            groupSize = 0
        }
    }

    if len(result) > 0 && result[len(result)-1] == '-' {
        result = result[:len(result)-1]
    }

    for left, right := 0, len(result)-1; left < right; left, right = left+1, right-1 {
        result[left], result[right] = result[right], result[left]
    }

    return string(result)
}

The Go implementation follows the same algorithmic structure as the Python version, but there are a few language-specific details.

Go strings are immutable, so we use a []byte slice as a mutable buffer. Appending to a byte slice is efficient and avoids repeated allocations.

Uppercase conversion is done manually using ASCII arithmetic because we are only dealing with English letters.

Since Go does not provide a built-in reverse function for slices, the solution reverses the slice in place using a two-pointer swap loop.

Worked Examples

Example 1

Input:

s = "5F3Z-2e-9-w"
k = 4

After ignoring dashes and processing backward:

Step	Character	Action	Result Buffer	Group Size
1	w	append W	W	1
2	-	skip	W	1
3	9	append 9	W9	2
4	-	skip	W9	2
5	e	append E	W9E	3
6	2	append 2	W9E2	4
7	group full	append dash	W9E2-	0
8	-	skip	W9E2-	0
9	Z	append Z	W9E2-Z	1
10	3	append 3	W9E2-Z3	2
11	F	append F	W9E2-Z3F	3
12	5	append 5	W9E2-Z3F5	4
13	group full	append dash	W9E2-Z3F5-	0

Remove trailing dash:

W9E2-Z3F5

Reverse:

5F3Z-2E9W

Final answer:

"5F3Z-2E9W"

Example 2

Input:

s = "2-5g-3-J"
k = 2

Step	Character	Action	Result Buffer	Group Size
1	J	append J	J	1
2	-	skip	J	1
3	3	append 3	J3	2
4	group full	append dash	J3-	0
5	-	skip	J3-	0
6	g	append G	J3-G	1
7	5	append 5	J3-G5	2
8	group full	append dash	J3-G5-	0
9	-	skip	J3-G5-	0
10	2	append 2	J3-G5-2	1

Reverse:

2-5G-3J

Final answer:

"2-5G-3J"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed once
Space	O(n)	The result buffer stores the reformatted string

The algorithm scans the input string exactly once. Every character is appended to the result buffer at most one time, and the final reverse operation is also linear.

The space complexity is linear because we must store the reformatted string separately from the input.

Test Cases

solution = Solution()

assert solution.licenseKeyFormatting("5F3Z-2e-9-w", 4) == "5F3Z-2E9W"  # provided example 1

assert solution.licenseKeyFormatting("2-5g-3-J", 2) == "2-5G-3J"  # provided example 2

assert solution.licenseKeyFormatting("abc", 3) == "ABC"  # exact group size

assert solution.licenseKeyFormatting("abc", 2) == "A-BC"  # shorter first group

assert solution.licenseKeyFormatting("---a---", 1) == "A"  # many dashes

assert solution.licenseKeyFormatting("a-a-a-a-", 1) == "A-A-A-A"  # k equals 1

assert solution.licenseKeyFormatting("abcd-efgh", 4) == "ABCD-EFGH"  # already formatted

assert solution.licenseKeyFormatting("abcd-efgh", 8) == "ABCDEFGH"  # single group result

assert solution.licenseKeyFormatting("a", 1) == "A"  # smallest valid input

assert solution.licenseKeyFormatting("----ab", 2) == "AB"  # leading dashes only

assert solution.licenseKeyFormatting("2-4A0r7-4k", 4) == "24A0-R74K"  # mixed letters and digits

assert solution.licenseKeyFormatting("2", 2) == "2"  # single character with large k

Test	Why
"5F3Z-2e-9-w", 4	Validates standard formatting behavior
"2-5g-3-J", 2	Validates shorter first group
"abc", 3	Checks exact divisibility
"abc", 2	Checks uneven grouping
"---a---", 1	Ensures dashes are ignored correctly
"a-a-a-a-", 1	Tests smallest grouping size
"abcd-efgh", 4	Tests already formatted structure
"abcd-efgh", 8	Ensures single-group output works
"a", 1	Smallest valid input
"----ab", 2	Tests leading dashes
"2-4A0r7-4k", 4	Mixed alphanumeric validation
"2", 2	Single character edge case

Edge Cases

One important edge case occurs when the number of alphanumeric characters is exactly divisible by k. In this situation, the backward-building process appends a trailing dash after the final group. If this dash is not removed before reversing, the output would incorrectly begin with a dash. The implementation handles this by checking whether the final character in the buffer is '-' and removing it before reversal.

Another important case is when the input contains many unnecessary dashes, such as "---a---". A naive implementation might accidentally preserve empty groups or create malformed output. The algorithm completely ignores all dashes during traversal, ensuring that only valid alphanumeric characters participate in grouping.

A third edge case occurs when k = 1. In this scenario, every character must become its own group. Some implementations incorrectly insert extra separators or mishandle the first group. Because this solution inserts a dash after every processed character group of size k, it naturally produces the correct format without any special-case logic.

A final edge case involves lowercase letters mixed with digits, such as "2-4A0r7-4k". Forgetting uppercase conversion would produce incorrect output. The implementation converts every non-dash character to uppercase immediately before insertion, guaranteeing consistent formatting throughout the result.