Java Solution using 2D array to store letter occurrences (17ms)


  • 4
    J

    The for-loop for end is executed for at most 26 times under each start. So, since we consider 26 as a constant, the loops take O(n).

    However, thanks to @StefanPochmann, I noticed that my indexOf() takes O(n) time too, so it is O(n^2) in worst case.

    First, traverse the string to store how many times each letter has occurred from 0 to i.
    Then, find the longest working substring starting at each position, with the starting point from left to right.

    The key to not get TLE is to start with the longest, then (1) if the long substring does not work, cut its tail to exclude the letter that makes it not working (2) obviously, if the long substring works, no need to check its substrings shorter than it (3) [most important to get "aaaaaaa....a" test case to work] if s.length() - start is already smaller than the known working longest substring, we are done.

    By the way, as I have commented, I could have deleted some characters that didn't appear at all to decrease the constant.

    public class Solution {
        public int longestSubstring(String s, int k) {
            if (s == null || s.length() < 1) return 0;
    
            int[][] letters = new int[26][s.length() + 1];
            for (int i = 0; i < s.length(); i++) {
                for (int c = 0; c < 26; c++) {
                    letters[c][i+1] = letters[c][i];
                }
                letters[s.charAt(i) - 'a'][i+1] += 1;
            }
            // May also optimize by deleting letters entries with 0 at end
            
            int longest = 0;
            for (int start = 0; start < s.length(); start++) {
                if (longest >= s.length() - start) return longest;
                for (int end = s.length(); end > start; end--) {
                    boolean works = true;
                    for (int c = 0; c < 26; c++) {
                        int num = letters[c][end] - letters[c][start];
                        if (num < k && num > 0) {
                            works = false;
                            end = s.indexOf('a' + c, start) + 1;
                            break;
                        }
                    }
                    if (works) {
                        if (end - start > longest) longest = end - start;
                        break;
                    }
                }
            }
    
            return longest;
        }
    }
    

  • 0
    F

    Time complexity O(N^2)?


  • 0
    J

    @fatalme I think it is O(n) even if it looks like O(n^2). Because the for-loop for 'end' is executed for at most 26 times. So, since we consider 26 as a constant, it is O(n).


  • 0
    C

    Nice solution!


  • 0
    L

    Wonderful solution. It is a good trade off. O(26N) space to keep the cost below O(26N). I came up with this idea as well. Only problem is we don't generally construct auxilary reference like this, because the space might be huge. For example, if the character is UTF-16,....


  • 1

    No, it's not O(n). For example for test cases like s = "a" * m + "b" + "c" * m and k = 2, you'll try every 'a' as start character and the complexity for your indexOf calls (to find the darn 'b') adds up to Θ(m^2) = Θ(n^2).


  • 0
    J

    @StefanPochmann You are right! I forgot to count indexOf in.


Log in to reply
 

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