[Remove All Adjacent Duplicates in String II] What is the time/space complexity of this solution?
MichalZ
50

I solved Remove All Adjacent Duplicates in String II (https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/) problem this way. Now I'm trying to understand what is its time/space complexity.

I think Time Complexity is O(N * N/k) because of nested loops. Outer loop can execute at most N/k times and inner loop can execute N times. and Space Complexity is O(N/k) because of Set which can grow up to N/k elements. Is that correct?
I'm assuming N is the length of the input string.

    public String removeDuplicates(String s, int k) {
        if(s == null || s.isEmpty()) {
            return s;
        }
        
        String currWord = s;
        
        while(true) {
		    // this set will contain start indices of substrings that should be removed
            Set<Integer> indicesToRemove = new HashSet<>();
            char prevChar = currWord.charAt(0);
            int currLen = 1;
            // go over a string char by char and count same consecutive sequence length
			// if there is a sequence with length == k then add its start position to the Set
            for(int i = 1; i < currWord.length(); i++) {
                char currChar = currWord.charAt(i);
                if(currChar == prevChar) {
                    currLen++;
                    if(currLen == k) {
                        indicesToRemove.add(i - k + 1);
                        currLen = 1;
                    }
                } else {
                    prevChar = currChar;
                    currLen = 1;
                }
            }
            // set is empty so we can get out of the infinite loop because there is nothing more to be removed
            if(indicesToRemove.isEmpty()) {
                break;
            }
            
            StringBuilder sb = new StringBuilder();
            // create a new string by skipping characters that should be removed
            int idx = 0;
            while(idx < currWord.length()) {
                if(indicesToRemove.contains(idx)) {
                    idx += k;
                }
                if(idx < currWord.length()) {
                    sb.append(currWord.charAt(idx));
                }
                idx++;
            }
            // continue the process with new string
            currWord = sb.toString();
        }
        
        return currWord;
    }
Comments (0)