#482

Easy

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

License Key Formatting

Reformat a license key string by splitting into groups of size k, converting to uppercase, and handling dashes appropriately.

string

Problem Statement

You are given a license key represented as a string s, consisting of alphanumeric characters and dashes. The string is divided into n + 1 groups by n dashes. Additionally, you are given an integer k.

You must reformat the string s such that each group contains exactly k characters, except for the first group which can be shorter but must still contain at least one character. Insert a dash between groups and convert all lowercase letters to uppercase.

Examples

Example 1

Input: s = "5F3Z-2e-9-w", k = 4

Output: "5F3Z-2E9W"

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"

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 Approach

Iterate and build the result

Iterate through the characters in the input string s, ignore the dashes, and append characters to form groups. Track the number of characters in each group, ensuring they conform to the specified size k.

Handle the first group

For the first group, ensure it can be shorter than k, but must contain at least one character. This requires careful management of the group's length during the iteration.

Convert to uppercase and manage dashes

During the iteration, convert all characters to uppercase. As groups are formed, insert dashes between them, except before the first group.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

The time complexity is O(N), where N is the length of the input string s, as we iterate through the string once. The space complexity is O(1) because we use constant extra space beyond the output string.

What Interviewers Usually Probe

The candidate correctly identifies a string-driven solution pattern.
The candidate demonstrates an understanding of how to handle edge cases like the first group.
The candidate implements the uppercase conversion and dash management effectively.

Common Pitfalls or Variants

Common pitfalls

Failing to handle the first group properly, leading to incorrect group sizes.
Incorrectly placing dashes or leaving extra ones at the end of the string.
Not converting lowercase letters to uppercase as specified in the problem.

Follow-up variants

Reformatting strings with different delimiters (e.g., spaces, commas).
Handling a string with no dashes, where groups must still be formed.
Adjusting the number of groups or the size of each group dynamically.

FAQ

What is the best approach for solving the License Key Formatting problem?

The best approach is to iterate over the string, build groups, handle the first group separately, and manage the conversion to uppercase and insertion of dashes.

How can I avoid extra dashes when formatting the license key?

Ensure that you only insert dashes between groups and not at the start or end of the string.

What is the time complexity of the License Key Formatting problem?

The time complexity is O(N), where N is the length of the input string s.

Can I use built-in functions for string manipulation in this problem?

Yes, built-in string manipulation functions like upper() and join() can help simplify the implementation.

What should I focus on when solving problems like License Key Formatting?

Focus on managing string groups, handling edge cases with the first group, and ensuring accurate formatting throughout.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        n = len(s)
        cnt = (n - s.count("-")) % k or k
        ans = []
        for i, c in enumerate(s):
            if c == "-":
                continue
            ans.append(c.upper())
            cnt -= 1
            if cnt == 0:
                cnt = k
                if i != n - 1:
                    ans.append("-")
        return "".join(ans).rstrip("-")

Continue Practicing

#481 magical string #488 zuma game #474 ones and zeroes