482. License Key Formatting

Google

Problem

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 <= 105
• s consists of English letters, digits, and dashes '-'.
• 1 <= k <= 104

Solution

Right To Left - O(n) time - O(1) space

#include<string>
 
using namespace std;
 
class Solution {
public:
    string licenseKeyFormatting(string s, int k) {
        string result = "";
        int count = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s[i] != '-') {
                result.push_back(toupper(s[i]));
                count++;
                if (count % k == 0) result.push_back('-');
            }
        }
        if (result.size() > 0 && result.back() == '-') result.pop_back();
        reverse(result.begin(), result.end());
        return result;
    }
};

Left to right - O(n) time - O(n) space

1. Initialize:
   • count to 0, which is used to count the number of characters in the current group.
   • n to input string length.
   • ans to an empty string, which is used to store the final result.
2. Now, iterate on the input string in reverse order:
   • We will skip '-' characters from the input string.
   • If the current character is not '-', we include the current character in ans string and increment the current group size by incrementing count by 1.
   • If count reaches k, it means we formed a group of size k, thus we can append a '-' in ans now, and reset count to start counting a new group.
3. After we finish traversing on the input string, we should check if the last character inserted wasn’t a dash. If we find a dash we need to remove it from ans string.
4. Now that we formed all groups in reverse order, thus we need to reverse the ans string and then return it.

class Solution {
public:
    string licenseKeyFormatting(string s, int k) {
        int totalChars = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] != '-') {
                totalChars++;
            }
        }
        
        int sizeOfFirstGroup = (totalChars % k);
        if (sizeOfFirstGroup == 0) {
            sizeOfFirstGroup = k;
        }
        
        string ans = "";
        int i = 0;
        int count = 0;
        
        while (i < s.length()) {
            if (count == sizeOfFirstGroup) {
                count = 0;
                break;
            }
            if (s[i] != '-') {
                count++;
                ans.push_back(toupper(s[i]));
            }
            i++;
        }
        /* This case will only appear if the value of k is greater than the total number of alphanumeric characters in string s */
        if (i >= s.length()) {
            return ans;
        }
        
        ans.push_back('-');
        
        while (i < s.length()) {
            if (s[i] != '-') {
                /* Whenever count is equal to k, we put a '-' after each group*/
                if (count == k) {
                    ans.push_back('-');
                    count = 0;
                }
                ans.push_back(toupper(s[i]));
                count++;
            }
            i++;
        }
        return ans;
    }
};