educative.io

Educative

Space complexity is O(1)

The space complexity should be O(1), since the maximum number of distinct characters is limited by the character encoding (e.g. ASCII, UTF-8, etc.), not by K. Thus the maximum size of the hashmap is O(1).

Hi @Alexander_T,
Space complexity will be O(1) as mentioned by George.
If we use only 26 chars then the count map will be of max size 26 whatever the input string length or the arg K is. Hashmap will take extra space but it doesn’t grow as per input arg K.
Replace the map with count array of 26/ASCII/UNICODE charset size for better understanding.
Thanks

1 Like

Thanks for that explanation. I was wondering how it was constant but the approach you’ve mentioned does help bringing the space from K to constant.