Why using ASCII encoding isnt a constant time? why should we convert it to string and compare? cant we simply compare the integers?
Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Solution: Repeated DNA Sequences
1 Like
Hello @Rami_Mankevich,
Thank you for sharing this feedback. Let me address your query regarding the constant time operation and conversion of characters.
If the ASCII encoding for two k-length substrings is the same, we can not be certain that those k-length substrings will be equal since ASCII encoding only ensures the same frequency of characters, not the arrangement. Therefore, when a duplicate ASCII value is encountered it’s necessary to convert back to the k-length substring to compare if they’re actually identical.
Also, ASCII encoding is indeed a constant time operation. The linear aspect (O(k)) comes from the need to convert back to a k-length substring and comparing if a duplicate is encountered.
You can take a look at the contents under the heading “Hashing and comparison in linear time” for a much better understanding with examples.
Feel free to share more suggestions and feedback. We’d be happy to help. Thanks!
Happy learning!