A few days ago my friend asked me a question, How can we find the longest substring which contains 2 unique characters in linear time without additional memory?
Yeah, we spoke about algorithms 🙂. I suggested to use 2 cursors like start and end and just get substring by these cursors. Generally idea is right, but how can we manage these cursors ? This is quite hard. Maybe not so hard but need some time to think about it.
OK, what do we have ?
1) we have input string like next abcc;
2) we should not use additional memory, it means we can store some indexes (like start and end cursors), maybe some additional points, but cannot clone input string or use some data – structure to manage string, I mean trie tree and/or so on.
3) complexity should be linear
OK, we have all information about algorithm and can start development. Yes, firstly I’ve provided these implementation after that he told me about algorithm Kadane.
Yes, we should modify it, but idea is great, ok lets go to implementation:
I am using next variables:[crayon-5bf04f0c161ef799177294/] Instead of Set we can use two Characters, but it’s more readable use Set and store just 2 chars in it.
Start and End these are two cursors I’ve written above and maxString is result string of the our algorithm.
All steps in implementation are easy but I want to draw your attention to method moveStart. This implementation contains simple trick 🙂. But I think all of you can understand it !!!
OK, testing code (maybe there are some problems in code I’ve tested on a few test data)
[crayon-5bf04f0c161f8637782337/] Looks like working in linear time 🙂