Watch 10 video solutions for License Key Formatting, a easy level problem involving String. This walkthrough by Kevin Naughton Jr. has 16,160 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105s consists of English letters, digits, and dashes '-'.1 <= k <= 104Problem Overview: You receive a license key string containing alphanumeric characters and dashes. The goal is to remove existing dashes, convert letters to uppercase, and regroup characters so the first group may be shorter while the rest contain exactly k characters separated by dashes.
Approach 1: Iterative Approach with StringBuilder (O(n) time, O(n) space)
This approach processes the string in a single forward pass after removing dashes. First, iterate through the original string and build a cleaned version containing only alphanumeric characters while converting letters to uppercase. Then compute the size of the first group using len % k. Append the first group (if non-zero) and continue appending the remaining characters in blocks of k, inserting dashes between groups. A StringBuilder or dynamic string buffer avoids repeated string concatenation, keeping the operation linear. This method is easy to reason about because the grouping logic follows the final formatted order.
The algorithm performs a simple scan and controlled appends, making it a good example of practical string manipulation. You touch each character once during cleaning and once during grouping, so the total runtime remains O(n) with O(n) auxiliary space for the result.
Approach 2: Reverse and Append Approach (O(n) time, O(n) space)
The reverse-building technique simplifies grouping logic by working from the end of the string. Iterate backward through the original string, skipping dashes and converting characters to uppercase. Maintain a counter that tracks how many characters have been added to the current group. Every time the counter reaches k, append a dash before continuing the next group.
Since characters are appended in reverse order, the result must be reversed at the end. The key insight is that grouping from the end guarantees that all groups except possibly the first naturally contain exactly k characters. This removes the need to precompute the first group length. The technique resembles a simple string traversal pattern often used in formatting and parsing tasks.
Recommended for interviews: Both solutions run in O(n) time and O(n) space, which is the expected optimal complexity. The reverse-and-append method tends to be cleaner because it avoids calculating the first group length explicitly. Still, demonstrating the forward iterative approach shows you understand grouping logic and controlled string construction. Interviewers typically expect a linear pass using a buffer structure rather than repeated string concatenation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Approach with StringBuilder | O(n) | O(n) | When you want straightforward forward traversal and explicit control over the first group size |
| Reverse and Append Approach | O(n) | O(n) | When grouping from the end simplifies logic and avoids computing the first group length |