Two basic solutions in C++, without any explanation


  • 1

    Brute-force

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int count[256]{0}, len = s.length(), maxLen = 1;
            if(len < 2) return len;
            for(int i = 0; i < len-maxLen; ++i){
                memset(count, 0, sizeof(int)*256);
                int j = i;
                for(; j < len; ++j){
                    if(count[s[j]]++ == 1){
                        maxLen = max(maxLen, j-i);
                        break;
                    }
                }
                if(j == len) maxLen = max(maxLen, j-i);
            }
            return maxLen;
        }
    };
    

    Trick

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int count[256]{0}, l = 0, r = 0;
            int len = s.length(), maxLen = 0;
            while(r < len){
                if(count[s[r]] < 1) count[s[r]]++;
                else{
                    maxLen = max(maxLen, r-l);
                    while(count[s[r]]) count[s[l++]]--;
                    count[s[r]]++;
                }
                r++;
            }
            maxLen = max(maxLen, r-l);
            return maxLen;
        }
    };
    

  • 1
    L

    @LHearen Your tricky solution is very similar to my foremost Java solution, which records times of character.

    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int[] hash = new int[256];
            char[] sc = s.toCharArray();
            
            int size = 0, max = 0;
            int i = 0, j = 0, k = 0;
            while (i < sc.length) {
                while(j < sc.length) {
                    if (++hash[(int)sc[j++]] == 2) break;
                    ++size;
                }
                max = Math.max(max, size);
                while (k < j) {
                    if (--hash[(int)sc[k++]] == 1) break;
                    --size;
                }
                i = j;
            }
            return max;        
        }
    }
    

    But I think we only need to record the last index of character, and here is my C code.

    int lengthOfLongestSubstring(char *s) {
        int max = 0, i = 0, j = 0, l;
        
        int hash[128] = {0};
        for (; s[j] != '\0'; j++) {
            if (hash[s[j]] != 0) {
                max = (l=j-i)>max ? l : max;
                i = hash[s[j]]>i ? hash[s[j]] : i;
            }
            hash[s[j]] = j+1;
        }
        
        return (l=j-i)>max ? l : max;
    }
    

Log in to reply
 

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