O(n) time O(1) space solution using Kadane's algo in Java


  • 20
    Z

    Idea is that, while we traverse form left to right if we see a character at position j is a duplicate of a character at a position i < j on the left then we know that we can't start the substring from i anymore. So, we need to start a new substring from i+1 position. While doing this we also need to update the length of current substring and start of current substring. Important part of this process is to make sure that we always keep the latest position of the characters we have seen so far. Below is a simple O(n) implementation of this logic.

    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int lastIndices[] = new int[256];
            for(int i = 0; i<256; i++){
                lastIndices[i] = -1;
            }
            
            int maxLen = 0;
            int curLen = 0;
            int start = 0;
            int bestStart = 0;
            for(int i = 0; i<s.length(); i++){
                char cur = s.charAt(i);
                if(lastIndices[cur]  < start){
                    lastIndices[cur] = i;
                    curLen++;
                }
                else{
                    int lastIndex = lastIndices[cur];
                    start = lastIndex+1;
                    curLen = i-start+1;
                    lastIndices[cur] = i;
                }
                
                if(curLen > maxLen){
                    maxLen = curLen;
                    bestStart = start;
                }
            }
            
            return maxLen;
        }
    }

  • 0
    T

    Amazing! It took me more than half an hour to understand your algorithm! How could you come up with this solution! awesome!


  • 0
    Z

    tricky part is to maintain start of current substring. Else the idea is similar to Kadane's algorithm.


  • 0
    M

    I have the same solution but use a HashMap instead of array given that HashMap lookup is O(1). What do you think?


  • 0
    Z

    HashMap look up is O(1) only if the keys are amortized and we use consistent hashing. In worst case, a HashMap has an O(n) lookup. But for simple keys like individual character it is O(1) anyway as the hash is always unique for characters ASCII value.

    Also, by default hashmap starts with size 16 and keeps doubling its size in case the map is loaded by more than 75% of its capacity. So, if we have a character set of many characters then we are unnecessarily doing some extra computation for resizing the hashmap.

    One solution is that we instantiate hashMap with capacity equals the number of characters in the character set.


  • 0
    _

    I'm sorry to bother you,but I hope you can help me.I can't understand why the length of lastIndices is 256.


  • 0
    Z

    With 8 bit character set a character ascii value can assume 0 to 255 ( 2^8 -1) . So there are 256 unique values a character can have.


  • 0
    M

    You can remove beststart variable because you never use it.


  • 0
    S

    Why do you have bestStart?


  • 0
    C

    So brilliant idea, successfully convert it in Python, Thanks a lot !


  • -2
    N

    Great Solution.
    But I guess I will ask an obvious question: how is this o(1) space if you are defining int array of size 256


  • 0
    Z

    A constant is always O(1). Regardless of number of input n, the space is constant 256. For Thai reason space complexity is O(1). I hope this help in clarifying your confusion about algorithmic order.


  • 0
    S

    Oddly enough, I tried instantiating the HashMap with size 256 and it actually slowed my runtime down by 3-7ms (result varies), compared with using the default size and allowing the HashMap to resize itself.


  • 0
    A

    That's not true constant space. What if it's a Unicode string? You end up with increasing the char array size, however a constant space solution should not change depending on the input size.


  • 0
    K

    How is this O(1) space? People have done the same thing in an extremely less complex way.


  • 0
    P

    This is probably the best solution at this point.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.