Code running into problematic test case. Any comments would be appreciated!


  • 0
    M
    public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int maxsubStringSize = 0;
            HashSet<Character> curString = new HashSet<Character>();
            int curSize = 0;
            
            for ( int i = 0; i < s.length() - maxsubStringSize; i++ )
            {
                char c = s.charAt(i);
                // Add character not already in current candidate
                if ( !curString.contains(c) )
                {
                    curString.add(c);
                }
                else
                {
                    // Check the current candidate for maxness
                    if ( curString.size() > maxsubStringSize )
                        maxsubStringSize = curString.size();
                        
                    // Clear the candidate and start at the next starting index
                    curString.clear();
                    i = i - curString.size();
                }
            }
            
            return maxsubStringSize;
        }
    }
    

    Problematic test case:

    Input: "hnwnkuewhsqmgbbuqcljjivswmdkqtbxixmvtrrbljptnsnfwzqfjmafadrrwsofsbcnuvqhffbsaqxwpqcac"
    Output: 11
    Expected: 12
    

    I had a previously "correct" answer that didn't use hashsets, but the complexity was too large, so this is my second attempt with an O(1) "contains" lookup. If I can get this to work it'll be O(n).


Log in to reply
 

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