The License Key Formatting Algorithm in C++

You are given a license key represented as a string S which consists only alphanumeric character and dashes. The string is separated into N+1 groups by N dashes.

Given a number K, we would want to reformat the strings 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.

Given a non-empty string S and a number K, format the string according to the rules described above.

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.
Note:
The length of string S will not exceed 12,000, and K is a positive integer.
String S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9) and dashes(-).
String S is non-empty.

Given a string, you are asked to form a license key with each group containing K letters except the first one may be less. Groups are separated by the dash.

String Concatenation is Memory-consuming

We can scan backwards from the end of the string, when we have multiples of the K characters, we add a dash in the front. The edge case will be to remove the leading dashes. However, the following implementation results in a memory-limited-exceeded error because the string concatenation in C++ is memory-and-time-costly which may require allocating spaces for new string and copying out the original strings.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    string licenseKeyFormatting(string S, int K) {
        string output = "";
        int j = 0;
        for (int i = S.length() - 1; i >= 0; --i) {
            if (S[i] == '-') continue;
            output = string(1, toupper(S[i])) + output;
            if ((++j) % K == 0) {
                output = "-" + output;
            }
        }
        return output[0] == '-' ? output.substr(1) : output;
    }
};

class Solution {
public:
    string licenseKeyFormatting(string S, int K) {
        string output = "";
        int j = 0;
        for (int i = S.length() - 1; i >= 0; --i) {
            if (S[i] == '-') continue;
            output = string(1, toupper(S[i])) + output;
            if ((++j) % K == 0) {
                output = "-" + output;
            }
        }
        return output[0] == '-' ? output.substr(1) : output;
    }
};

The time complexity is O(N^2) i.e. considering the string allocation process may require copying characters over each concatenation process ((1+2+3+…N) and the space complexity is O(1).

Pre-allocated Char Array

To speed up and reduce the memory consumption, we can pre-allocate a character array which is twice big as the size of origin string i.e. if the K is one, the license key is length 3 for string of 2, and length 7 for string of 4 i.e. 2n-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    string licenseKeyFormatting(string S, int K) {
        const int MAX = S.length() * 2;
        char output[MAX];
        int k = MAX - 1;
        int j = 0;
        for (int i = S.length() - 1; i >= 0; --i) {
            if (S[i] == '-') continue;
            output[k --] = toupper(S[i]);
            if ((++j) % K == 0) {
                output[k --] = '-';
            }
        }
        int len = MAX - k - 1;
        string xx(len, ' ');
        for (int i = 0; i < len; ++ i) {
            xx[i] = output[k + i + 1];
        }
        return xx[0] == '-' ? xx.substr(1) : xx;
    }
};

class Solution {
public:
    string licenseKeyFormatting(string S, int K) {
        const int MAX = S.length() * 2;
        char output[MAX];
        int k = MAX - 1;
        int j = 0;
        for (int i = S.length() - 1; i >= 0; --i) {
            if (S[i] == '-') continue;
            output[k --] = toupper(S[i]);
            if ((++j) % K == 0) {
                output[k --] = '-';
            }
        }
        int len = MAX - k - 1;
        string xx(len, ' ');
        for (int i = 0; i < len; ++ i) {
            xx[i] = output[k + i + 1];
        }
        return xx[0] == '-' ? xx.substr(1) : xx;
    }
};

After populating the character array, we know the length of the target license key string, we need to pre-allocate a string with exact length and copying over each character. The time complexity is O(N) and space complexity is O(N).

–EOF (The Ultimate Computing & Technology Blog) —