{x}
blog image

License Key Formatting

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

Solution Explanation for License Key Formatting

This problem requires reformatting a license key string according to a given group length k. The solution involves several steps:

  1. Preprocessing:

    • Remove hyphens from the input string s.
    • Convert all characters to uppercase.
    • Calculate the number of characters (n) after removing hyphens. This is crucial for determining the length of the first group.

  2. Grouping:

    • Determine the length of the first group. This might be less than k if n is not a multiple of k. The remainder of n divided by k gives this length (or k if the remainder is 0).
    • Iterate through the processed string and build the formatted string. Add characters to the formatted string until the current group reaches length k.
    • Insert a hyphen after each group (except possibly the last group).

  3. Postprocessing:

    • Remove any trailing hyphen if present.
    • Return the formatted string.

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input string. The algorithm iterates through the string at most once for preprocessing and grouping.
  • Space Complexity: O(n) in the worst case, as the formatted string might have the same length as the input string. In some implementations, the space used might be slightly more due to intermediate string manipulations (but still linearly proportional to the input size).

Code Implementation in Different Languages

The following code implementations demonstrate the solution in Python, Java, C++, Go, and TypeScript. Each implementation follows the steps outlined above. Note that slight variations in syntax and handling of string manipulation exist across languages.

Python3

class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        s = s.upper().replace("-", "")
        n = len(s)
        first_group_len = n % k or k  # Length of the first group
        res = [s[:first_group_len]]  #Start with the first group
 
        for i in range(first_group_len, n, k):
            res.append(s[i:i+k])
        
        return "-".join(res)

Java

class Solution {
    public String licenseKeyFormatting(String s, int k) {
        s = s.toUpperCase().replaceAll("-", "");
        int n = s.length();
        int firstGroupLen = n % k == 0 ? k : n % k;
        StringBuilder sb = new StringBuilder(s.substring(0, firstGroupLen));
        for (int i = firstGroupLen; i < n; i += k) {
            sb.append("-").append(s.substring(i, i + k));
        }
        return sb.toString();
    }
}

C++

class Solution {
public:
    string licenseKeyFormatting(string s, int k) {
        string processed_s = "";
        for (char c : s) {
            if (c != '-') {
                processed_s += toupper(c);
            }
        }
        int n = processed_s.length();
        int first_group_len = n % k;
        if (first_group_len == 0) first_group_len = k;
        string result = processed_s.substr(0, first_group_len);
        for (int i = first_group_len; i < n; i += k) {
            result += "-" + processed_s.substr(i, k);
        }
        return result;
    }
};

Go

func licenseKeyFormatting(s string, k int) string {
	s = strings.ToUpper(strings.ReplaceAll(s, "-", ""))
	n := len(s)
	firstGroupLen := n % k
	if firstGroupLen == 0 {
		firstGroupLen = k
	}
	result := s[:firstGroupLen]
	for i := firstGroupLen; i < n; i += k {
		result += "-" + s[i:i+k]
	}
	return result
}

TypeScript

function licenseKeyFormatting(s: string, k: number): string {
    s = s.toUpperCase().replaceAll("-", "");
    let n = s.length;
    let firstGroupLen = n % k;
    if (firstGroupLen === 0) firstGroupLen = k;
    let result = s.substring(0, firstGroupLen);
    for (let i = firstGroupLen; i < n; i += k) {
        result += "-" + s.substring(i, i + k);
    }
    return result;
}

These implementations offer a concise and efficient solution to the license key formatting problem. They prioritize readability while maintaining good performance. The choice of language depends on the programmer's preference and the context of the application.