Why my program is still TLE?[JAVA]


  • 0
    G
      public class Solution {
    	
        
        public int lengthOfLongestSubstring(String s) {
        	int maxLen = 0;
        	int tmpLen = 0;
        	int length = s.length();
        	HashMap<Character, Integer>alphabet = new HashMap<Character,Integer>();
        	for (int i = 0; i < length; i++) {
        		char item = s.charAt(i);
    			if (!alphabet.containsKey(item)) {
    				tmpLen ++;
    				alphabet.put(item, i);
    			}
    			else {
    				if (maxLen < tmpLen) {
    					maxLen = tmpLen;
    				}
    				tmpLen = i - alphabet.get(item);
    				alphabet.put(item, i);
    			}
    		}
            if (maxLen < tmpLen) {
    			maxLen = tmpLen;
    		}
        	return maxLen;		
        }
    }
    

    I test it in my local machine and it costs 270ms.I don't konw why my program is stil TLE.


  • 0
    Z

    I have read your codes briefly. I think your algorithm is O(n) complexlty, but the function containsKey of HashMap also is O(n) complexlty. So your algorithm is O(n^2) complexlty in fact.


  • 0
    Y

    containsKey function of a HashMap should be O(1), not O(n)


  • 0
    Z

    In a worst condition that Hash collision occurs in each insertion operation!


  • 0
    L

    I met the same problem.
    And what's more the problem doesn't said all the character are based on ascii...
    So i think using a 128 length array is not strictly correct.
    But the Character range is too big...at least 2^16


Log in to reply
 

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