LeetCode 482: License Key Formatting

Problem Restatement

We are given a string s representing a license key and an integer k.

The string contains letters, digits, and dashes.

We need to reformat it so that:

For example:

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

After removing dashes and uppercasing:

5F3Z2E9W

Group from the right into chunks of size 4:

5F3Z 2E9W

Answer:

"5F3Z-2E9W"

Input and Output

Function shape:

def licenseKeyFormatting(s: str, k: int) -> str:
    ...

Examples

Example 1:

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

Remove dashes:

5F3Z2e9w

Uppercase:

5F3Z2E9W

Group into size 4 from the right:

5F3Z-2E9W

Answer:

"5F3Z-2E9W"

Example 2:

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

Remove dashes:

25g3J

Uppercase:

25G3J

Group from the right:

2-5G-3J

Answer:

"2-5G-3J"

First Thought: Clean Then Group

A direct solution has two phases.

First, build a clean string by removing dashes and converting letters to uppercase.

clean = []

for ch in s:
    if ch != "-":
        clean.append(ch.upper())

Then insert dashes so that groups from the right have length k.

This works, but inserting from the front can be awkward because the first group may be shorter.

Key Insight

Groups are easiest to build from the right.

Every group except the first must contain exactly k characters. That means if we scan the cleaned characters from right to left, we can add a dash after every k characters.

For example:

5F3Z2E9W

Read from the right:

W 9 E 2 | Z 3 F 5

After every 4 characters, insert a dash.

Then reverse the final result:

5F3Z-2E9W

This avoids separately computing the first group size.

Algorithm

Create an empty list ans.

Set count = 0.

Scan s from right to left.

For each character:

1. Skip it if it is a dash.
2. If count > 0 and count % k == 0, append a dash to ans.
3. Append the uppercase version of the character.
4. Increment count.

At the end, reverse ans and join it into a string.

Correctness

The algorithm ignores all original dashes, so old grouping has no effect on the result.

It processes all non-dash characters from right to left. Since every complete group except possibly the first must contain k characters, adding a dash after every k processed characters creates exactly the required grouping from the right.

The condition:

count > 0 and count % k == 0

adds a dash only between groups. It never adds a dash before the first processed character from the right.

Every appended letter is converted to uppercase, and digits stay unchanged.

After reversing the built list, the character order becomes the original left-to-right order, with dashes inserted between valid groups. Therefore, the returned string satisfies all formatting rules.

Complexity

Implementation

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

        for ch in reversed(s):
            if ch == "-":
                continue

            if count > 0 and count % k == 0:
                ans.append("-")

            ans.append(ch.upper())
            count += 1

        return "".join(reversed(ans))

Code Explanation

The result is built in reverse:

ans = []

The variable count tracks how many real characters have been added, excluding dashes.

count = 0

We scan from right to left:

for ch in reversed(s):

Old dashes are skipped:

if ch == "-":
    continue

Before adding a new character, we check whether the previous group already has k characters:

if count > 0 and count % k == 0:
    ans.append("-")

Then we add the uppercase character:

ans.append(ch.upper())

Finally, reverse the result because we built it from right to left:

return "".join(reversed(ans))

Testing

def run_tests():
    s = Solution()

    assert s.licenseKeyFormatting("5F3Z-2e-9-w", 4) == "5F3Z-2E9W"
    assert s.licenseKeyFormatting("2-5g-3-J", 2) == "2-5G-3J"
    assert s.licenseKeyFormatting("abc", 3) == "ABC"
    assert s.licenseKeyFormatting("abc", 2) == "A-BC"
    assert s.licenseKeyFormatting("--a-a-a-a--", 2) == "AA-AA"
    assert s.licenseKeyFormatting("----", 3) == ""

    print("all tests passed")

run_tests()

Test meaning: