I initially thought this problem would require fancy algorithms, but I ended up using what I consider the simplest approach.

Let me explain my thought process.

At first, I was a bit confused and naively thought: start enumerating from the first element of the array, and if a later element is different from the “first” element, stop and move to the next loop, then output the maximum sum.

Obviously that’s wrong! It should be: a later element must be different from ALL previous elements.

WA #1.

OK, this brute force approach did pass. Now, the problem says “characters” – if we’re talking about English letters including both upper and lower case, that’s 26*2. All ASCII characters would be 256. I allocated an array of 300, which should be enough.

The logic was correct but I still got WA #2. Why? Because the termination condition wasn’t explicit enough. If there are no repeating characters all the way to the end, my program would break.

WA #3 was because the program would crash when there’s only one element. Boundary conditions matter a lot for simple problems!

Finally it was pending for a while – I kept thinking it would time out, but it didn’t.

Yay!

Actually, the time complexity can be further optimized. If we start searching from position x, and elements at positions i and j are the same, the next search can start from i+1 instead of x+1. This would keep the time at linear scanning, though we’d need to store the indices of i and j.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int sum = 0;
        if(s.length() == 1)
            return 1;
        for(int i = 0; i < s.length(); i++)
        {
            int flag[300];
            for(int k = 0; k < 300; k++)
            {
                flag[k] = 0;
            }
            flag[s[i]] = 1;
            for(int j = i+1; j < s.length(); j++)
            {
                if(flag[s[j]] == 1)
                {
                    if(j - i > sum)
                        sum = j - i;
                    break;
                }
                if(j == s.length() - 1)
                {
                    if(j - i + 1 > sum)
                        sum = j - i + 1;
                    break;
                }
                flag[s[j]] = 1;
            }
        }
        return sum;
    }
};