algoadvance

Leetcode 482. License Key Formatting

Problem Statement

You are given a string s that consists of alphanumeric characters and dashes. The string is separated into groups by dashes. You are also given an integer k.

The task is 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 should be no lowercase letters in the final formatted string — convert them to uppercase.

Return the reformatted string.

Example

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

Input: s = "2-5g-3-J", k = 2
Output: "2-5G-3J"

Clarifying Questions

  1. Q: Can there be leading or trailing dashes in the input string? A: No, the input string won’t have leading or trailing dashes.

  2. Q: Will the input string always be valid and contain only alphanumeric characters and dashes? A: Yes, the input will be valid as per the problem statement.

  3. Q: Should the solution consider edge cases such as very small or very large values of k? A: Yes, ensure to handle such edge cases where k could be 1 or much larger than the length of processed string.

Strategy

  1. Clean the Input: Remove all dashes from the string and convert all characters to uppercase.
  2. Determine the First Group Length: Calculate the length of the first group. It might be shorter than k.
  3. Reformat the String:
    • Start from the beginning and form the first group with the calculated length.
    • Continue forming groups of k characters each until the end of the string.
    • Insert dashes between each group.
  4. Edge Cases: Handle cases where the length of the input string is smaller than or equal to k.

Code

Here is the implementation in C++:

#include <iostream>
#include <string>
#include <algorithm>

std::string licenseKeyFormatting(std::string s, int k) {
    // Remove dashes and convert to uppercase
    std::string cleaned;
    for (char c : s) {
        if (c != '-') {
            cleaned += std::toupper(c);
        }
    }

    // Calculate the length of the first group
    int firstGroupLength = cleaned.size() % k;
    
    // Result string
    std::string result;
    int count = 0;

    // Form the first group if there are leftover characters
    for (int i = 0; i < cleaned.size(); ++i) {
        result += cleaned[i];
        count++;
        // If we reach the first group or the groups of size `k`
        if ((count == firstGroupLength && firstGroupLength != 0) || (count == k && firstGroupLength == 0)) {
            // Avoid placing dash at the end
            if (i != cleaned.size() - 1) {
                result += '-';
            }
            count = 0;
            firstGroupLength = 0; // Reset first group length after processing it
        } else if(count == k) {
            // Avoid placing dash at the end
            if (i != cleaned.size() - 1) {
                result += '-';
            }
            count = 0;
        }
    }
    
    return result;
}

int main() {
    std::string s = "5F3Z-2e-9-w";
    int k = 4;
    std::string formatted = licenseKeyFormatting(s, k);
    std::cout << "Formatted key: " << formatted << std::endl; // Output: "5F3Z-2E9W"
    return 0;
}

Time Complexity

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