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 redefine s:
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?
The 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.