JAVA - Brute Force-Sliding Window Hybrid (Time Limit Exceeded)


  • 0
    E

    I'm not a traditional CS academic guru but I've been in the software engineering field for a while. To the explanation though!

    I approached this problem as, I would like to calculate the longest substring but in order to do that, I need to actually count the substring to determine if it is the longest or not and keeping the characters "in order" to do this became an assumption to accurately answer the question.

    With the use of a List collection (which preserves the order), the procedure was to:

    i) read the string character by character

    ii) if the list already contained the character, find the index where the first character is positioned, and reset the list from 1 + the position from where the value was originally indexed (firstPosition) to the end of the list, then add the would-be duplicate value to the list. Else just add the value to the list.

    III) Check the size of the list to the variable 'largest.' If the size of the updated list is greater than 'largest', the variable is updated to the size of the updated list.

    iv) Repeat.

    So the string 'abcdeaf' the list would be (at the 5th iteration):
    ['a', 'b', 'c', 'd', 'e'] and largest = 5.

    at the 6th iteration the list would be: ['b', 'c', 'd', 'e', 'a', 'f'] and largest = 6.

    (The longest substring is computed, the order preserved).

    Below is my source.

    public static int lengthOfLongestSubstring(String s) {
        int index = 0;
        int largest = 0;
        int listSize = 0;
        List<Object> uniqueChars = new ArrayList<>();
    
        char c;
    
        int length = s.length();
    
        while (index < length) {
            c = s.charAt(index);
            if (!uniqueChars.contains(c)) {
                uniqueChars.add(c);
            }
            else {
    
                //a repeat was found
                listSize = uniqueChars.size();
                if (listSize > largest)
                    largest = listSize;
    
                //remove all elements up to the first repeated character
                int firstRepeatIndex = uniqueChars.indexOf(c);
    
                //if the next element after the first element that was already stored ('bb') make a new list
                if ( (firstRepeatIndex + 1) >= uniqueChars.size())
                    uniqueChars = new ArrayList<>();
                else //otherwise resume appending unique elements to the list
                    uniqueChars = uniqueChars.subList(firstRepeatIndex + 1, uniqueChars.size());
    
                //resume
                uniqueChars.add(c);
            }
    
            if ( (index+1) >= length) {
                listSize = uniqueChars.size();
                if (listSize > largest)
                    largest = listSize;
            }
            ++index;
        }
    
        return largest;
    }
    

Log in to reply
 

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