# License Key Formatting
**Difficulty:** EASY
[External](https://leetcode.com/problems/license-key-formatting)
Canonical: https://scaleengineer.com/dsa/problems/license-key-formatting
**Data structures:** String
---
## Problem
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 <= 105`
* `s` consists of English letters, digits, and dashes `'-'`.
* `1 <= k <= 104`

# Approaches
## Clean and Rebuild
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`.
**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.
**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.
### Explanation
The core idea is to separate the problem into two distinct steps: data preparation and formatting.

1.  **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()`.

2.  **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.

```java
public class Solution {
    public String licenseKeyFormatting(String s, int k) {
        // 1. Clean the string: remove dashes and convert to uppercase.
        String cleanedS = s.replace("-", "").toUpperCase();
        int len = cleanedS.length();
        if (len == 0) {
            return "";
        }

        StringBuilder result = new StringBuilder();

        // 2. Calculate the length of the first group.
        int firstGroupLen = len % k;
        if (firstGroupLen == 0) {
            firstGroupLen = k;
        }

        // 3. Append the first group.
        result.append(cleanedS.substring(0, firstGroupLen));

        // 4. Append the rest of the groups.
        for (int i = firstGroupLen; i < len; i += k) {
            result.append("-");
            result.append(cleanedS.substring(i, i + k));
        }

        return result.toString();
    }
}
```
### 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`.

## Single Pass Traversal from Right to Left
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.
**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).
**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.
### Explanation
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.

```java
public class Solution {
    public String licenseKeyFormatting(String s, int k) {
        StringBuilder result = new StringBuilder();
        int count = 0;

        // Iterate from the end of the string to the beginning.
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == '-') {
                continue;
            }

            // If we have a full group, append a dash first.
            if (count == k) {
                result.append('-');
                count = 0;
            }

            result.append(Character.toUpperCase(c));
            count++;
        }

        // The result is built in reverse, so we need to reverse it at the end.
        return result.reverse().toString();
    }
}
```
### 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.

# Solutions
### Java

```java
class Solution {
public
  String licenseKeyFormatting(String s, int k) {
    s = s.replace("-", "").toUpperCase();
    StringBuilder sb = new StringBuilder();
    int t = 0;
    int cnt = s.length() % k;
    if (cnt == 0) {
      cnt = k;
    }
    for (int i = 0; i < s.length(); ++i) {
      sb.append(s.charAt(i));
      ++t;
      if (t == cnt) {
        t = 0;
        cnt = k;
        if (i != s.length() - 1) {
          sb.append('-');
        }
      }
    }
    return sb.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string licenseKeyFormatting(string s, int k) {
    string ss = "";
    for (char c : s) {
      if (c == '-')
        continue;
      if ('a' <= c && c <= 'z')
        c += 'A' - 'a';
      ss += c;
    }
    int cnt = ss.size() % k;
    if (cnt == 0)
      cnt = k;
    int t = 0;
    string res = "";
    for (int i = 0; i < ss.size(); ++i) {
      res += ss[i];
      ++t;
      if (t == cnt) {
        t = 0;
        cnt = k;
        if (i != ss.size() - 1)
          res += '-';
      }
    }
    return res;
  }
};

```

### Python

```python
class Solution:
    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)

```