Domain 1EasyCORE

License Key Formatting

The problem requires us to reformat a given license key string `S` according to specific rules. The input consists of a string `S` containing alphanumeric characters and dashes (`-`). The goal is to split the string into groups such that each group contains exactly `K` characters, except for possibly the first group which can be shorter but must contain at least one character. Additionally, all lowercase letters should be converted to uppercase, and there must be a dash inserted between two groups.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 0

482. License Key Formatting

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 43.1%


Problem Breakdown

The problem requires us to reformat a given license key string S according to specific rules. The input consists of a string S containing alphanumeric characters and dashes (-). The goal is to split the string into groups such that each group contains exactly K characters, except for possibly the first group which can be shorter but must contain at least one character. Additionally, all lowercase letters should be converted to uppercase, and there must be a dash inserted between two groups.

Inputs:

  • A non-empty string S consisting of alphanumeric characters and dashes.
  • An integer K representing the size of each group.

Outputs:

  • A reformatted string with groups of K characters separated by dashes.

Implicit Constraints or Tricky Edge Cases:

  • The first group can be shorter than K.
  • The string may contain leading or trailing dashes that need to be ignored.
  • The string could be entirely made up of dashes, resulting in an empty output after removing them.
  • The length of the string S will not exceed 12,000 characters.

Intuition

A brute-force approach would involve iterating through the string and manually constructing groups while handling the conversion to uppercase. However, this approach is inefficient due to its complexity and potential for errors in edge case handling.

The key insight is to first remove all dashes from the string and convert it to uppercase. Then, we can start forming groups of K characters from the end of the string towards the beginning. This way, we ensure that the first group can be shorter than K if necessary, and we handle the grouping in a straightforward manner.

Approach

  1. Remove Dashes and Convert to Uppercase:

    • Iterate through the string S and build a new string without dashes.
    • Convert all characters to uppercase during this process.
  2. Form Groups of K Characters:

    • Initialize an empty list to store the groups.
    • Starting from the end of the cleaned string, take chunks of up to K characters at a time.
    • Append each chunk to the list of groups.
  3. Join Groups with Dashes:

    • Reverse the list of groups to maintain the correct order.
    • Join the groups using dashes and return the resulting string.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input string S. We iterate through the string a constant number of times.
  • Space Complexity: O(n), as we store the cleaned string and the list of groups, both of which can be up to the length of the input string.

Solution

def licenseKeyFormatting(S: str, K: int) -> str:
    # Step 1: Remove dashes and convert to uppercase
    cleaned = ''.join(c.upper() for c in S if c != '-')
    
    # Step 2: Form groups of K characters from the end
    groups = []
    while cleaned:
        groups.append(cleaned[-K:])
        cleaned = cleaned[:-K]
    
    # Step 3: Join groups with dashes and return
    return '-'.join(reversed(groups))

Edge Cases Handled

  • Empty Input: The input string S is guaranteed to be non-empty, so this case does not apply.
  • All Dashes: If the input string contains only dashes, the cleaned string will be empty, resulting in an empty output after joining groups.
  • Single Character Groups: If the length of the cleaned string is less than or equal to K, the first group will naturally be shorter than K.
  • Leading/Trailing Dashes: These are ignored during the cleaning process, ensuring they do not affect the final output.