Code Implementation

class Solution:
    def licenseKeyFormatting(self, S: str, K: int) -> str:
        # Remove dashes and convert to uppercase
        S = S.replace('-', '').upper()
        size = len(S)
        # Find the size of the first group
        first_group = size % K
        groups = []
        if first_group:
            groups.append(S[:first_group])
        # Process the rest of the groups
        for i in range(first_group, size, K):
            groups.append(S[i:i+K])
        return '-'.join(groups)
      

class Solution {
public:
    string licenseKeyFormatting(string S, int K) {
        string s;
        // Remove dashes and convert to uppercase
        for (char c : S) {
            if (c != '-') s += toupper(c);
        }
        int size = s.size();
        string res;
        int first_group = size % K;
        int i = 0;
        if (first_group) {
            res += s.substr(0, first_group);
            i = first_group;
        }
        while (i < size) {
            if (!res.empty()) res += '-';
            res += s.substr(i, K);
            i += K;
        }
        return res;
    }
};
      

class Solution {
    public String licenseKeyFormatting(String S, int K) {
        S = S.replace("-", "").toUpperCase();
        int size = S.length();
        int firstGroup = size % K;
        StringBuilder sb = new StringBuilder();
        if (firstGroup != 0) {
            sb.append(S.substring(0, firstGroup));
        }
        for (int i = firstGroup; i < size; i += K) {
            if (sb.length() > 0) sb.append("-");
            sb.append(S.substring(i, i + K));
        }
        return sb.toString();
    }
}
      

var licenseKeyFormatting = function(S, K) {
    S = S.replace(/-/g, '').toUpperCase();
    let size = S.length;
    let firstGroup = size % K;
    let groups = [];
    if (firstGroup !== 0) {
        groups.push(S.slice(0, firstGroup));
    }
    for (let i = firstGroup; i < size; i += K) {
        groups.push(S.slice(i, i + K));
    }
    return groups.join('-');
};
      

Problem Description

Given a string S representing a license key and an integer K, reformat the string so that:

• All the alphanumeric characters are grouped into groups of size K, except possibly the first group which may be shorter but must contain at least one character.
• Groups are separated by dashes '-'.
• All lowercase letters are converted to uppercase.
• Existing dashes in S are ignored and should not appear in the output unless as group separators.

The solution must return the reformatted license key as a string.

Thought Process

At first glance, the problem seems to require a lot of string manipulation. One could try to process the string while keeping track of dashes and group sizes, but that quickly becomes messy. Instead, a better approach is to first remove all dashes and convert all letters to uppercase, so we only have a clean string to work with.

Once we have the cleaned string, the next challenge is to split it into groups of size K. The first group might be shorter, but all groups after that must be exactly of size K. By calculating the length of the first group, we can easily iterate over the rest of the string in steps of K.

This eliminates the need for complex state tracking and allows us to build the result group by group, joining them with dashes at the end.

Solution Approach

• Step 1: Remove all existing dashes from the input string S. This gives us only the alphanumeric characters.
• Step 2: Convert all letters in the string to uppercase. This ensures uniform formatting.
• Step 3: Determine the size of the first group. If the total length of the cleaned string is not a multiple of K, the first group will be shorter (specifically, len % K characters).
• Step 4: Use a loop to slice the string into groups: the first group (if any), then each subsequent group of size K.
• Step 5: Collect all groups into a list or string builder, and join them with dashes to form the final formatted license key.

This approach is efficient because it only processes the string a constant number of times, and avoids unnecessary complexity by treating the string as a sequence of characters rather than dealing with dashes as they appear in the original input.

Example Walkthrough

Let's consider the input S = "2-5g-3-J" and K = 2.

• Step 1: Remove dashes: We get "25g3J".
• Step 2: Convert to uppercase: "25G3J".
• Step 3: Length is 5. The first group size is 5 % 2 = 1 (so first group has 1 character).
• Step 4: First group: "2". Remaining: "5G3J".
• Step 5: Next group: "5G". Next group: "3J".
• Step 6: Join with dashes: "2-5G-3J".

The output is "2-5G-3J".

Time and Space Complexity

Brute-force approach: If we tried to process the string character by character, inserting dashes as needed, the complexity could still be O(N), but the implementation would be more complicated and error-prone.

Optimized approach (as described above):

• Time Complexity: O(N), where N is the length of the input string S. We process each character a constant number of times (removing dashes, converting to uppercase, grouping).
• Space Complexity: O(N), since we store the cleaned string and the resulting groups, both of which could be up to length N.

Summary

The key insight for this problem is to simplify the input by removing dashes and converting to uppercase first, which makes grouping straightforward. By calculating the size of the first group, we can efficiently split the string and join the groups with dashes. This approach is both easy to understand and efficient, making it an elegant solution to the License Key Formatting problem.