C++ (9ms) and Java (5ms) solutions O(n) time, O(1) space


  • 5
    S

    Basic idea is that the length of the longest substring ending at position i is the lesser of

    • the length of the longest substring ending at position i - 1 plus one
    • i - prevIndexOf[s[i]] i.e. the number of characters since the previous occurrence of the character at position i

    In the implementations below, i - prevIndexOf[c] is actually the number of characters since the last occurrence of c minus 1. This makes it convenient to compare it to the length of the longest substring ending at position i - 1 and add one to the lesser of the two in order to obtain the length of the longest substring ending at position i.

    C++ implementation

    int lengthOfLongestSubstring(string s) {
      int maxLen = 0, prevMaxLen = 0, prevIndexOf[128] = {0};
      for (int i = 0; i < s.length(); i++) {
        int curMaxLen = min(prevMaxLen, i - prevIndexOf[s[i]]) + 1;
        prevIndexOf[s[i]] = i + 1;
    
        if (curMaxLen > maxLen) {
          maxLen = curMaxLen;
        }
        prevMaxLen = curMaxLen;
      }
      return maxLen;
    }
    

    Same algorithm in Java

    int lengthOfLongestSubstring(String s) {
      int maxLen = 0, prevMaxLen = 0;
      int[] prevIndexOf = new int[128];
      for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        int curMaxLen = Math.min(prevMaxLen, i - prevIndexOf[c]) + 1;
        prevIndexOf[c] = i + 1;
    
        if (curMaxLen > maxLen) {
          maxLen = curMaxLen;
        }
        prevMaxLen = curMaxLen;
      }
            
      return maxLen;
    }
    

Log in to reply
 

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