Find Palindromes in an array of strings in Java

Question

Hello I am trying to find the palindromes in an array of strings . I have tried the brute force method with O(n2) time complexity

 for(int i=0;i<s.length;i++) {
            for(int j=i+1;j<s.length;j++) {
                if(s[i] == reverse(s[j])) {
                    count++;
                }
            }
        }

I am looking for a solution without using hashing and with O(n) time complexity or a better time complexity .

My problem is if I am on a particular index , I have to compare the element at that index with the remaining elements .

can anyone please help me solve this questions. TIA

Answer 1

You can check the String as Palindrome or not in single loop , in O(n), only by iterating from both ends like compare first with last, second with second-last and so on like :-

String st1 = "RACECAR";
int flag=0;   
    for (int j=0;j<=str1.length()-1 ;j++)   
    {   
     if (st1.charAt(j)!=st1.charAt(st1.length()-j-1))   
     {   
     flag=1;   
     break;   
     }   
    }  
  if(flag==1)   
  System.out.println("String is not a palindrome");   
  else   
    System.out.println("String is a palindrome"); 

Output :- String is a palindrome