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.
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.
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 == '-' 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 == '-' 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
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.
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.