Java O(n^2) Faster than 100% of other Java submissions


  • 1
    E

    Solution is based on the fact that there are only two possible "cores" of Palindromes.
    An Even length palindrome will have a "core" in the format of "aa".
    An Odd length palindrome will have a "core" in the format of "aba".

    We find all cores, and check if adding one character before and after the core still produces a Palindrome.

            //Two cases:
        	//substring length:
        	// 		Even :    aa
        	//		Odd:      aba
    
        	char[] string = s.toCharArray();
        	int minIndex = 0;
        	int maxIndex = string.length-1;
        	
        	//get indices of Even (size 2):
        	ArrayList<Integer> even = new ArrayList<Integer>();
        	for(int i = 0; i <= string.length-2; i++)
        	{
        		if(string[i] == string[i+1])
        		{
        			even.add(i);
        		}
        	}
        	
        	//get indices of Odd (size 3):
        	ArrayList<Integer> odd = new ArrayList<Integer>();
        	for(int i = 0; i <= string.length-3; i++)
        	{
        		if(string[i] == string[i+2])
        		{
        			odd.add(i+1);
        		}
        	}
          
        	int ans = 0;
        	
        	//every single char is a palindrome
        	ans = ans + string.length;
        	
        	//palindrome of size 2
        	ans = ans + even.size();
        
        	//palindrome of size 3
        	ans = ans + odd.size();
        	
        	
        	for(Integer mid : even)
        	{
        		int size = 1;
        		while(mid-size >= minIndex && mid + 1 + size <= maxIndex)
        		{
        			if(string[mid-size] == string[mid+1+size])
        			{
        				ans++;
        				size ++;
        			}
        			else break;
        		}
        	}  	
        	
        	for(Integer mid : odd)
        	{
        		int size = 2;
        		while(mid-size >= minIndex && mid + size <= maxIndex)
        		{
        			if(string[mid-size] == string[mid+size])
        			{
        				ans++;
        				size ++;
        			}
        			else break;
        		}
        	}
        	
        	return ans;
        '''

Log in to reply
 

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