What is the time complexity of this solution?


  • 0
    P
    public String longestPalindrome(String s) {
    	int maxStart = 0;
    	int maxEnd = 0;
    
    	for (int middle1 = 0; middle1 < s.length(); middle1++) {
    		for (int middle2 = middle1; middle2 <= middle1 + 1; middle2++) {
    			int radius = -1;
    			int i = middle1;
    			int j = middle2;
    			while (i >= 0 && j < s.length()) {
    				if (s.charAt(i--) == s.charAt(j++)) {
    					radius++;
    				} else {
    					break;
    				}
    			}
    			
    			if (radius * 2 + (middle2 - middle1) > maxEnd - maxStart) {
    				maxStart = middle1 - radius;
    				maxEnd = middle2 + radius;
    			}
    		}
    	}
    	
    	return s.substring(maxStart, maxEnd + 1);
    }

  • 0
    T

    This problem can be implemented in O(n), but the data structure would be complex, called suffix tree automaton.


Log in to reply
 

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