Why is my solution inefficient? (Timeout)


  • 0
    P
    public class Solution {
        public String longestPalindrome(String s) {
            
            if(s == null) {
                throw new RuntimeException("Invalid string.");
            }
            
            if(s.isEmpty() || s.length() == 1) {
                return s;
            }
            
            String max = s.substring(0, 1);
            int cur = 0;
            int prev = -1;
            int post = 1;
            
            while(cur < s.length()) {
                if(prev >= 0 && (s.charAt(cur) == s.charAt(prev))) {
                    int ptr1 = prev;
                    int ptr2 = cur;
                    while(ptr1 >= 0 && ptr2 < s.length() && 
                            (s.charAt(ptr1) == s.charAt(ptr2))) {
                        ptr1--;
                        ptr2++;
                    }
                    
                    if((ptr2 - ptr1 - 1) > max.length()) {
                        if(ptr1 < 0) {
                            max = s.substring(ptr2);
                        } else {
                            max = s.substring(ptr1 + 1, ptr2);
                        }
                    }
                    
                }
                
                if(prev >= 0 && post < s.length() && (s.charAt(post) == s.charAt(prev))) {
                    int ptr1 = prev;
                    int ptr2 = post;
                    while(ptr1 >= 0 && ptr2 < s.length() && 
                            (s.charAt(ptr1) == s.charAt(ptr2))) {
                        ptr1--;
                        ptr2++;
                    }
                    
                    if((ptr2 - ptr1 - 1) > max.length()) {
                        if(ptr1 < 0) {
                            max = s.substring(ptr2);
                        } else {
                            max = s.substring(ptr1 + 1, ptr2);
                        }
                    }
                    
                }
                
                cur++;
                prev++;
                post++;
            }
            
            return max;
            
        }
        
    }

Log in to reply
 

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