Slow O(n^2) solution executed fast and didn't get TLE


  • 0

    I was thinking about how this problem reminded me about regular expressions with character classes and alternatives and came up with the following NFA-based solution:

    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int max = s.length() == 0 ? 0 : 1;
        int[][] start = new int[2][s.length()];
        char[][] char1 = new char[2][s.length()];
        int[][] char2 = new int[2][s.length()];
        int statesLen = 0, nextLen;
        int current = 0, next = 1;
        for (int i = 0; i < s.length(); ++i) {
            nextLen = 0;
            char c = s.charAt(i);
            start[next][nextLen] = i;
            char1[next][nextLen] = c;
            char2[next][nextLen] = -1;
            ++nextLen;
            for (int j = 0; j < statesLen; ++j) {
                boolean continues = char1[current][j] == c || char2[current][j] == c;
                boolean mutates = char2[current][j] == -1;
                if (continues || mutates) {
                    if (i - start[current][j] + 1 > max) {
                        max = i - start[current][j] + 1;
                    }
                    start[next][nextLen] = start[current][j];
                    char1[next][nextLen] = char1[current][j];
                    char2[next][nextLen] = continues ? char2[current][j] : c;
                    ++nextLen;
                }
            }
            statesLen = nextLen;
            // swap arrays
            current = 1 - current;
            next = 1 - next;
        }
        return max;
    }
    

    I was able then optimize most of this stuff away to constant memory and linear time (4 ms, 98%), but what surprised me is that this solution executed in 11 ms and beat about 78%. If you look at it, it becomes clear that it is quadratic time in the worst case. And the worst case is when the input string consists of only one repeating character. It then keeps adding duplicate states to the array and the whole thing just blows up.

    Maybe it's worth adding a corner test case for this? One 50000 character string consisting of one repeating char will do the trick.


Log in to reply
 

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