algoadvance

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.

You want 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.

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 with 4 characters.

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 with 2 characters except the first part as it could be shorter than 2.

Clarifying Questions

  1. Q: Can the input string s contain any characters other than alphanumeric characters and dashes? A: No, the string s will only contain alphanumeric characters and dashes.

  2. Q: In the output, should the first group ever be empty? A: No, the first group must contain at least one character.

Strategy

  1. Remove Dashes: Remove all existing dashes from the string s.
  2. Convert to Uppercase: Convert the entire string to uppercase.
  3. Divide into Groups: Starting from the end of the string, divide the string into groups of k characters. The first group may be shorter, depending on the remainder.
  4. Join with Dashes: Join the groups with dashes and return the result.

Code

def licenseKeyFormatting(s: str, k: int) -> str:
    # Remove all dashes and convert to uppercase
    s = s.replace('-', '').upper()
    
    # Initialize a list to hold the parts
    parts = []
    
    # Process the cleaned string from the end to the beginning
    while len(s) > k:
        parts.append(s[-k:])
        s = s[:-k]
    
    # Add the remaining part (which is the first group)
    parts.append(s)
    
    # Join the parts with dashes
    return '-'.join(parts[::-1])

# Example usage
print(licenseKeyFormatting("5F3Z-2e-9-w", 4))  # Output: "5F3Z-2E9W"
print(licenseKeyFormatting("2-5g-3-J", 2))     # Output: "2-5G-3J"

Time Complexity

The time complexity of the solution is O(N), where N is the length of the input string s. This is because we iterate through the string multiple times to remove dashes, convert to uppercase, and form the groups.

Space Complexity

The space complexity is also O(N) since we are storing parts of the string in a list, which in the worst case scenario, stores all characters from input s.

Try our interview co-pilot at AlgoAdvance.com