# 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:

| Rule | Meaning |
|---|---|
| Remove old dashes | Existing dashes do not matter |
| Convert letters | All letters become uppercase |
| Regroup characters | Groups are separated by dashes |
| Group size | Every group has exactly `k` characters, except maybe the first |
| First group | It may be shorter than `k`, but must contain at least one character |

For example:

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

After removing dashes and uppercasing:

```text
5F3Z2E9W
```

Group from the right into chunks of size `4`:

```text
5F3Z 2E9W
```

Answer:

```python
"5F3Z-2E9W"
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | String `s`, integer `k` |
| Output | Reformatted license key |
| Characters | English letters, digits, and dashes |
| Constraint | `1 <= s.length <= 10^5`, `1 <= k <= 10^4` |

Function shape:

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

## Examples

Example 1:

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

Remove dashes:

```text
5F3Z2e9w
```

Uppercase:

```text
5F3Z2E9W
```

Group into size `4` from the right:

```text
5F3Z-2E9W
```

Answer:

```python
"5F3Z-2E9W"
```

Example 2:

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

Remove dashes:

```text
25g3J
```

Uppercase:

```text
25G3J
```

Group from the right:

```text
2-5G-3J
```

Answer:

```python
"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.

```python
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:

```text
5F3Z2E9W
```

Read from the right:

```text
W 9 E 2 | Z 3 F 5
```

After every `4` characters, insert a dash.

Then reverse the final result:

```text
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:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the string once and reverse the result once |
| Space | `O(n)` | The output list stores the reformatted key |

## Implementation

```python
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:

```python
ans = []
```

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

```python
count = 0
```

We scan from right to left:

```python
for ch in reversed(s):
```

Old dashes are skipped:

```python
if ch == "-":
    continue
```

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

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

Then we add the uppercase character:

```python
ans.append(ch.upper())
```

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

```python
return "".join(reversed(ans))
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `"5F3Z-2e-9-w", 4` | Main example |
| `"2-5g-3-J", 2` | First group shorter than `k` |
| `"abc", 3` | One full group |
| `"abc", 2` | Short first group |
| `"--a-a-a-a--", 2` | Many old dashes |
| `"----", 3` | No real characters after removing dashes |