License Key Formatting code Challenge Leetcode

Question

This is the challenge:

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:

1) The length of string S will not exceed 12,000, and K is a positive integer.
2) String S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9) and dashes(-).
3) String S is non-empty.

Here is my Code:

public static String licenseKeyFormatting(String S, int Key) {
    String cleaned = S.replaceAll("[\\-]", "").toUpperCase();
    String result = "";
    int currentPos = 0;

    //IF EVENLY SPLIT
    if ( (cleaned.length() % Key) == 0 ) {
        int numGroups = cleaned.length()/Key;

        for(int i = 0; i < numGroups; i++) {
            for (int k =0; k < Key; k++) {
                char currentLetter = cleaned.charAt(currentPos++);
                result = result + currentLetter;
            }

            if (i != (numGroups - 1)) {
                result = result + "-";
            }
        }
    }

    else {

        int remainder = cleaned.length() % Key;

        for (int i = 0; i < remainder; i++) {
            char currentLetter = cleaned.charAt(currentPos++);
            result = result + currentLetter;
        }

        if(remainder == cleaned.length()) {
            return result;
        }
        else {
            result = result + "-";
        }

        int numGroups =( (cleaned.length() - remainder)/Key);

        for (int i = 0; i < numGroups; i++) {
            for (int k =0; k < Key; k++) {
                char currentLetter = cleaned.charAt(currentPos++);
                result = result + currentLetter;
            }
            if (i != (numGroups - 1)) {
                result = result + "-";
            }
        }
    }

    //IF NOT EVENLY SPLIT
    return result;
}

When I run it on my Computer, it works perfectly. When I run it on leetcode, it gives me a "Time Limit Exceeded" Error on the an input of a string of 44151 characters and "1" as the key. When I run the same input on my IDE, it works fine, but not on LeetCode. What might be the error? How could I make this more efficient?

Please provide the challenge rather than linking to the challenge. We really hate it when links become outdated! — Super Jade, Sep 11 '18 at 01:27

vermaji · Accepted Answer · 2018-09-11T02:51:00.370

1

I believe there is nothing wrong in program, but it is not the fast enough to meet time complexity expected by leetcode. I would suggest you can try, remove dashes and convert to upper cases. then add dashes at every (kth+remainder) places after the remainder position.

Do these operations in a stringbuilder instead of string.

edited Sep 11 '18 at 02:51

answered Sep 11 '18 at 02:40

vermaji

539
2
10

You mean `StringBuilder`, right? [`StringBuffer` is the older/slower version that does a lot of unnecessary synchronization, making it slower](https://stackoverflow.com/a/2771852/836214) (though still better than straight-up string concatenation in a loop) – Krease Sep 11 '18 at 02:45
Newer Java runtime engines are smart enough to see that the synchronization isn’t necessary if you use the `StringBuffer` inside one method only, so it doesn’t matter whether you use `StringBuilder` or `StringBuffer` in this case (my habit is to use `StringBuilder` too, though). – Ole V.V. Sep 11 '18 at 09:38
Your last sentence is probably the key. Without `StringBuilder`, it's damn slow as it creates tons of strings of lengths up to 40k. – maaartinus Sep 11 '18 at 10:47
Thank you so much! – cs123 Sep 11 '18 at 17:31
@cs123 wc. Please upwote the answer. – vermaji Sep 12 '18 at 11:04
@vermaji I did! unfortunately I don't have enough reputation points for it to show – cs123 Sep 17 '18 at 16:37

License Key Formatting code Challenge Leetcode

1 Answers1