algoadvance

Leetcode 482. License Key Formatting

Problem Statement

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 at least 1 character. Furthermore, there should be a dash inserted between two groups and all lowercase letters should be converted to uppercase.

Return the reformatted license key.

Example:

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:

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 mentioned before.

Clarifying Questions

1. Are the given inputs always valid?
   • Yes, the inputs are always valid as specified in the problem.
2. Are we allowed to use additional data structures?
   • Yes, you can use additional data structures as necessary for simplification.
3. Does the dash existing in the initial string count in the length of the final formatted groups?
   • No, only alphanumeric characters count towards the length of final formatted groups. The dashes are separators.
4. Is there a specific format for output (e.g., upper case)?
   • Yes, as mentioned, all characters should be converted to upper case.

Strategy

1. Remove Dashes and Convert to Uppercase:
   • Iterate through the string s, remove all the dashes, and convert any lowercase letters to uppercase.
2. Determine Grouping:
   • Calculate the size of the first group. This is given by len % k where len is the length of the string after removing dashes.
   • The remaining groups will each be of size k.
3. Build Final String:
   • Use a StringBuilder to construct the reformatted string by appending characters and adding dashes where necessary.

Code

public class LicenseKeyFormatting {
    public String licenseKeyFormatting(String s, int k) {
        // Remove all dashes and convert to uppercase
        StringBuilder cleanString = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c != '-') {
                cleanString.append(Character.toUpperCase(c));
            }
        }
        
        // Get the length of cleaned string
        int len = cleanString.length();
        int firstGroupLength = len % k == 0 ? k : len % k;
        
        StringBuilder result = new StringBuilder();
        int i = 0;
        
        // Append the first group
        result.append(cleanString.substring(i, i + firstGroupLength));
        i += firstGroupLength;
        
        // Append the remaining groups with dashes
        while (i < len) {
            result.append('-');
            result.append(cleanString.substring(i, i + k));
            i += k;
        }
        
        return result.toString();
    }
    
    public static void main(String[] args) {
        LicenseKeyFormatting formatter = new LicenseKeyFormatting();
        System.out.println(formatter.licenseKeyFormatting("5F3Z-2e-9-w", 4)); // Output: 5F3Z-2E9W
        System.out.println(formatter.licenseKeyFormatting("2-5g-3-J", 2));    // Output: 2-5G-3J
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of the input string. This accounts for processing each character to strip dashes and convert to uppercase, and for constructing the final string.

• Space Complexity: O(n), because we are storing the intermediate cleaned string and the final result string.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?