License Key Formatting

Easy

Google

6 views

Topics:

Strings

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.

We want to reformat the string s 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 you should convert all lowercase letters 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 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"
Explanation: 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 <= 10⁵
s consists of English letters, digits, and dashes '-'.
1 <= k <= 10⁴

Try coding it in LeetCode

License Key Formatting

Easy

Google

6 views

Topics:

Strings

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.

We want to reformat the string s 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 you should convert all lowercase letters 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 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"
Explanation: 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 <= 10⁵
s consists of English letters, digits, and dashes '-'.
1 <= k <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string S contain characters other than alphanumeric characters (letters and digits)?
Is the integer K always positive? What happens if K is zero or negative?
If after removing dashes from S, the resulting string's length is not a multiple of K, how should the first group be formatted?
Should the returned string always be in uppercase, or should I preserve the case of the alphanumeric characters from the input?
What should I return if the input string S is null or empty after removing all the dashes?

Brute Force Solution

Approach

The brute force approach tries all possible ways to format the license key. It involves testing different groupings of characters and separators until a valid format is found. This approach exhaustively explores all combinations.

Here's how the algorithm would work step-by-step:

First, remove all the dashes from the license key.
Now, consider all the ways to split the license key into groups of characters.
For each possible split, check if it meets the formatting requirements (all groups have length 'k' except possibly the first group).
If a split meets the requirements, insert dashes between the groups.
Convert the entire formatted key to uppercase.
Repeat this process for every possible way to split the license key.
From all the validly formatted keys, choose the first one or any one according to some pre-defined criteria.

Code Implementation

def license_key_formatting_brute_force(license_key, key_length):
    # Remove all dashes from the license key
    license_key_without_dashes = license_key.replace("-", "")

    all_formatted_keys = []
    
    # Iterate through all possible split positions
    for i in range(1 << (len(license_key_without_dashes) - 1)):
        formatted_key = ""
        group_length = 0
        current_group = ""
        valid_format = True
        
        for j in range(len(license_key_without_dashes)):
            current_group += license_key_without_dashes[j]
            group_length += 1
            
            if (i >> j) & 1:
                # This split point creates a group
                if group_length != key_length:
                    if j != len(license_key_without_dashes) -1:
                        valid_format = False
                        break
                formatted_key += current_group + "-"
                current_group = ""
                group_length = 0
        
        formatted_key += current_group
        
        if group_length > 0 and group_length != key_length and len(formatted_key.split('-')[-1]) != key_length:
            valid_format = False

        if valid_format:
            # Convert to uppercase if the format is valid
            formatted_key = formatted_key.upper()
            all_formatted_keys.append(formatted_key)

    if not all_formatted_keys:
        return ""
    
    # Return the first validly formatted key
    return all_formatted_keys[0]

Big(O) Analysis

Time Complexity

O(2^n) – Removing dashes takes O(n) time, where n is the length of the license key. The core of the brute force approach involves considering all possible ways to split the license key string. For a string of length n, there are 2^(n-1) possible splits. For each split, we need to verify if it adheres to the specified formatting rules, which requires iterating through the split groups, taking O(n) time in the worst case. Therefore, the overall time complexity is dominated by the splitting and verification steps, leading to a time complexity of O(n * 2^(n-1)), which simplifies to O(2^n).

Space Complexity

O(N) – The brute force approach described needs to store multiple potentially valid formatted license keys. In the worst-case scenario, many splits might meet the formatting requirements, and each valid key could have a length proportional to the input license key's length after removing dashes, which we can denote as N. Therefore, space is used to store potentially multiple strings of length up to N. This auxiliary space usage is directly proportional to the size of the input license key, leading to a space complexity of O(N).

Optimal Solution

Approach

The goal is to reformat a license key string by grouping characters into chunks of a specific size, separated by dashes. We work backward through the string to make it easier to form the groups correctly and efficiently.

Here's how the algorithm would work step-by-step:

First, remove all the dashes from the original license key string.
Then, convert all the characters in the string to uppercase.
Start building the reformatted string from the end of the processed string.
Take a chunk of characters from the end equal to the specified group size.
Add a dash before this chunk unless it's the very first chunk we are adding.
Repeat the previous two steps, moving towards the beginning of the string, until you have processed all the characters.
Finally, return the reformatted string.

Code Implementation

def format_license_key(license_key, group_size):
    processed_key = license_key.replace("-", "").upper()
    result = ""
    key_length = len(processed_key)

    # Iterate backwards to form groups of size K
    for i in range(key_length - 1, -1, -1):
        result = processed_key[i] + result

        # Add a dash after each group of K characters.
        if (key_length - i) % group_size == 0 and i != 0:
            result = "-" + result

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the license key string once to remove dashes and convert it to uppercase, which takes O(n) time, where n is the length of the original string. Reformatting the string involves iterating through the processed string once more, building the result in chunks. Therefore, the time complexity is dominated by these linear iterations over the string, resulting in O(n) time complexity, since the group size is constant.

Space Complexity

O(N) – The algorithm creates a new string to store the reformatted license key. In the worst-case scenario, where no dashes are present in the original string, the reformatted string will contain N characters (from the original string) plus dashes added between the groups. Therefore, the auxiliary space required to store this new string is proportional to the length of the input string, N. The space used to store the intermediate string and the uppercase version also depend on N. Thus, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input string S	Return an empty string immediately if the input string is null or empty.
Empty groups (K=0)	If K is zero, handle it as an invalid input and either return an empty string or throw an exception.
String S with only delimiters	Remove all delimiters, resulting in an empty string; return empty string.
String S with no letters or digits after removing delimiters	Remove all delimiters and non-alphanumeric characters, resulting in an empty string; return empty string.
K is larger than the length of the string after removing delimiters	Format the entire string into a single group without a leading delimiter.
String S contains lowercase letters that need to be capitalized	Convert the entire string to uppercase before formatting to ensure consistency.
Very long input string causing potential performance issues	Use StringBuilder for efficient string manipulation to avoid excessive object creation.
Input string with leading or trailing delimiters	Trim the string after removing all the existing hyphens and before creating groups.