O(n) Java concise solution


  • 0
    M

    The idea is pretty straightforward. We could iterate the string from the last char, and when we meet k characters, we append a '-' to the result string. During the process, we will ignore the misplaced '-'.

    public class Solution {
        public String licenseKeyFormatting(String S, int K) {
            StringBuilder sb = new StringBuilder();
            int i = S.length() - 1;
            while (i >= 0) {
                int cur = 0;
                while (cur < K && i >= 0) {
                    char c = S.charAt(i--);
                    if (c != '-') {
                        sb.append(Character.toUpperCase(c));
                        cur ++;
                    } 
                }
                sb.append('-');
            }
            i = sb.length() - 1;
            while (i >= 0 && sb.charAt(i) == '-') { // delete any leading dashs
                sb.deleteCharAt(i--);
            }
            return sb.reverse().toString();
        }
    }
    

  • 0
    V
    This post is deleted!

  • 0
    V

    @mgispk I dont get the part where you are deleting the leading dashes. I understand it will delete the leading dash, but wont it also delete the dash inserted after K ?


  • 0
    M

    @vicmania2007
    Think about this case str = "-AA-AA-AA", k = 2. After the first while loop, the output string will be: "AA-AA-AA--", because the first while loop doesn't stop when you end up with "AA-AA-AA-", it continues to read the last "-", and hence one more dash will be added. You can simple run the code with this test case to see why it happens. (Please note that the delete logic will end when we met first non-dash character).


  • 0
    V

    @mgispk My bad, "the delete logic will end when we met first non-dash character", it totally went out of my notice...Thanks!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.