Skip to main content
Talentd

License Key Formatting - Solution & Explanation

EasyString12 min readAsked at: Google
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Iterative Approach with StringBuilder

This approach involves first cleaning up the input string by removing all non-alphanumeric characters and converting it to uppercase. Then, starting from the end of the string, we build the new license key by appending groups of size k. This is achieved using a StringBuilder for efficient string manipulation.

We begin by removing all dashes and converting the string to uppercase. We calculate the remainder, which helps in determining the first group size that could be less than k. We use a loop to iterate through the cleaned-up string in steps of k and store these groups. Finally, we join the groups with a dash and return the result.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the string s. Space Complexity: O(n) due to the additional storage requirements for the new formatted string.

Try this approach in the editor →

Approach 2: Reverse and Append Approach

This method suggests reversing the cleaned-up string to easily extract groups from the end, and then reversing the result at the end. This eliminates the need for calculating the remainder at the start and allows straightforward appending of characters.

By reversing the process, we simplify grouping into steps of k directly from the end without needing any special handling for the first group. We maintain a counter to insert a dash after every k characters and finally reverse the accumulated result.

Code

JavaC++

Java

C++

Complexity

Time Complexity: O(n), where n is the length of s. Space Complexity: O(n) for storing the result string temporarily.

Try this approach in the editor →

Approach 3: Simulation

First, we count the number of characters in the string s excluding the hyphens, and take the modulus of k to determine the number of characters in the first group. If it is 0, then the number of characters in the first group is k; otherwise, it is the result of the modulus operation.

Next, we iterate through the string s. For each character, if it is a hyphen, we skip it; otherwise, we convert it to an uppercase letter and add it to the answer string. Meanwhile, we maintain a counter cnt, representing the remaining number of characters in the current group. When cnt decreases to 0, we need to update cnt to k, and if the current character is not the last one, we need to add a hyphen to the answer string.

Finally, we remove the hyphen at the end of the answer string and return the answer string.

The time complexity is O(n), where n is the length of the string s. Ignoring the space consumption of the answer string, the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Approach with StringBuilder

Time Complexity: O(n), where n is the length of the string s. Space Complexity: O(n) due to the additional storage requirements for the new formatted string.

Reverse and Append Approach

Time Complexity: O(n), where n is the length of s. Space Complexity: O(n) for storing the result string temporarily.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Approach with StringBuilderO(n)O(n)When you want straightforward forward traversal and explicit control over the first group size
Reverse and Append ApproachO(n)O(n)When grouping from the end simplifies logic and avoids computing the first group length

Video Solution

License Key Formatting • Kevin Naughton Jr. • 16,170 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is License Key Formatting easy or hard?
License Key Formatting is classified as an Easy problem on LeetCode. The challenge mainly tests careful string traversal, grouping logic, and handling edge cases like existing dashes or a shorter first group.
License Key Formatting Python/Java solution
Python solutions typically build the result using a list and join operation after grouping characters. Java implementations often rely on StringBuilder for efficient appends while scanning the string or constructing it in reverse. Both approaches run in O(n) time.
How to solve License Key Formatting in O(n)?
Traverse the string and ignore existing dashes while converting characters to uppercase. Append characters to a result buffer and insert a dash after every k characters when building from the end, or group characters after computing the first segment length. Both strategies process the string once, resulting in O(n) time.
What is the best approach for License Key Formatting?
The optimal approach scans the string once, removes dashes, converts characters to uppercase, and rebuilds the key in groups of size k. Many implementations use a reverse traversal with a counter that inserts a dash every k characters. This keeps the complexity O(n) time and O(n) space.
Is License Key Formatting asked at Google/Amazon/Meta?
License Key Formatting is a common string manipulation problem similar to formatting and parsing questions seen in interviews at large tech companies. Variants of string reformatting and grouping logic frequently appear in screening rounds at companies like Amazon and Google.
What data structure is used in License Key Formatting?
The primary structure used is a dynamic string buffer such as StringBuilder in Java or a list/buffer in Python. These allow efficient character appends while constructing the formatted result without repeated string concatenation.
What is the time complexity of License Key Formatting?
The problem can be solved in O(n) time where n is the length of the input string. Each character is processed at most once while skipping dashes and building the formatted result. Space complexity is O(n) because a new formatted string is created.

Ready to solve this problem?

Practice License Key Formatting with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring