educative.io

Space complexity seems incorrect here

Courses
,
#1

Shouldn’t the space complexity not be O(M), but O(26) which reduces to O(1)?

The maximum size of the hashmap is 26 because it can only contain lowercase letters, so it doesn’t scale directly with M. M could be smaller than 26, but that still makes O(26) (and therefore O(1)) the worst case.

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Solution Review: Problem Challenge 2 - Grokking the Coding Interview: Patterns for Coding Questions

#2

Hello @Codequiver,

Yes, you are right; in that particular case, when we talk about the case where only lowercase letters are involved, the space complexity will O(1).

Thank you for this insight. :blush: