Leetcode – License Key Formatting Solution in Python

The License Key Formatting problem is a classic algorithmic problem that can be found on Leetcode. This problem tests your string manipulation skills and is a great example to understand how to deal with strings in a more efficient way. In this article, we will go through the problem statement, discuss various approaches and their trade-offs, and analyze their complexities.

Problem Statement:

You are given a license key represented as a string s which consists of only alphanumeric characters and dashes. The string is separated into n + 1 groups by n dashes. Given an integer k, you need to reformat the string 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 all lowercase letters should be converted to uppercase.

Example:

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

Brute Force Approach:

A naive approach would be to iterate through the given string and build the result string by adding characters one by one while keeping a count of characters in the current group. When this count reaches k, append a dash to the result string and reset the count. Convert all the characters to uppercase before appending them to the result string.

def licenseKeyFormatting(s, k):
    result = ''
    count = 0
    
    # Iterate through the string in reverse
    for char in reversed(s):
        if char != '-':
            # Convert lowercase letters to uppercase
            result += char.upper()
            count += 1
            # Insert dashes
            if count % k == 0:
                result += '-'
    
    # The result string is in reverse, so reverse it back
    result = result[::-1]
    
    # Remove the leading dash if present
    return result[1:] if result and result[0] == '-' else result

However, this approach involves string concatenation in a loop which can be inefficient in Python as strings are immutable, and this could result in a new string being created at each iteration.

Optimized Approach using String Builder:

An optimized approach would be to use a list as a string builder instead of concatenating strings. This allows for more efficient appending of characters.

def licenseKeyFormatting(s, k):
    result = []
    count = 0
    
    # Iterate through the string in reverse
    for char in reversed(s):
        if char != '-':
            # Convert lowercase letters to uppercase
            result.append(char.upper())
            count += 1
            # Insert dashes
            if count % k == 0:
                result.append('-')
    
    # The result list is in reverse, so reverse it back
    result = result[::-1]
    
    # Convert the list to string and remove the leading dash if present
    result_str = ''.join(result)
    return result_str[1:] if result_str and result_str[0] == '-' else result_str

This approach is more efficient due to the mutable nature of lists in Python.

More Concise Approach:

We can make the code more concise by directly calculating the size of the first group. Once we have this, the rest of the groups will have exactly k characters.

def licenseKeyFormatting(s, k):
    # Remove dashes and convert to uppercase
    s = s.replace('-', '').upper()
    
    # Length of the first group
    first_group_len = len(s) % k or k
    
    result = [s[:first_group_len]]
    
    # Append the rest of the groups
    for i in range(first_group_len, len(s), k):
        result.append(s[i:i+k])
    
    # Join the groups with dashes
    return '-'.join(result)

This approach directly calculates the parts and joins them using dashes, making the code more concise and slightly more efficient by removing unnecessary checks.

Conclusion:

The License Key Formatting problem is an excellent practice problem for honing your string manipulation skills in Python. We discussed different solutions, including a naive approach and more optimized ones.