I have written a solution for the following problem: https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/
To summarise the question, we are given an
integer k, and we need to
remove duplicates of length k, from the
input string s.
In my solution, I write out all the possible duplicates, which is an array of 26 elements. Then I iterate over the input string s, and remove the duplicates from it, or rather, I use slicing to
def removeDuplicates(s: str, k: int) -> str: dup = [k * i for i in "qwertyuiopasdfghjklzxcvbnm"] pointer1 = 0 while pointer1+k<len(s): if s[pointer1:pointer1+k] in dup: s = s[:pointer1] + s[pointer1+k:] if pointer1>1: pointer1-=2*k if s[-k:len(s)] in dup: s = s[:-k] else: pointer1+=1 return s
My understanding is that the
time complexity is O(n), where n is the length of the input string, since in the worst case we iterate over the whole string without removing any characters. Is this correct?
space complexity is where I am more unsure, as each time I find a duplicate, I am redefining s, so will need to allocate ‘new’ space for this. Is it right to say that the space complexity is O(n) as well?
Actually, it depends on the language you are working on. Like java have garbage collector and similar thing is also there in python. But in c there we can say we have O(n) space complexity.