How would I modify this for an O(n) time complexity? Basically, my program just finds the palindrome string and outputs a statement based on the findings.

class ChkPalindrome
{
   public static void main(String args[])
   {
      String str, rev = "";
      Scanner sc = new Scanner(System.in);
 
      System.out.println("Enter a string:");
      str = sc.nextLine();
 
      int length = str.length();
 
      for ( int i = length - 1; i >= 0; i-- )
         rev = rev   str.charAt(i);
 
      if (str.equals(rev))
         System.out.println(str " is a palindrome");
      else
         System.out.println(str " is not a palindrome");
 
   }
}

CodePudding user response：

rev = rev str.charAt(i) is the culprit. This statement by itself takes O(N) time, N being the size of rev.

Given that this line is inside a for loop that runs N times, your code is O(N^2) time.

The fix is the same fix for when you want to append to a string inside loops: Don't do that, use StringBuilder instead:

StringBuilder reverse = new StringBuilder();
for (int i = length - 1; i >= 0; i--) {
  reverse.append(str.charAt(i));
}
if (str.contentEquals(rev)) {
 // palindrome
} else {
  // nope
}

Or, even faster (but by a constant factor with early exit, which both make a large difference in real life but don't affect O(N) numbers): Simply compare the first and last character, then the second-to-first and second-to-last, returning immediately with false if you see a mismatch. Also break up your methods (you should have a method that determines palindrome, and a separate method that then prints results). Something like:

boolean isPalindrome(String str) {
  int len = str.length(), mid = len / 2;
  for (int i = 0; i < mid; i  ) {
    char a = str.charAt(i);
    char b = str.charAt(len - i);
    if (a != b) return false;
  }
  return true;
}

// and then the code you have now simply becomes...
if (isPalindrome(str)) {
  System.out.println(str   " is a palindrome");
} else {
  System.out.println(str   " is not a palindrome");
}

Separate methods make them shorter, easier to read and understand, more re-usable, and easier to test.

CodePudding user response：

public static boolean isPalindrome(String str) {
    for(int i = 0, j = str.length() - 1; i < j; i  , j--)
        if(str.charAt(i) != str.charAt(j))
            return false;
    
    return true;
}

CodePudding user response：

StringBuilder reverse operation takes O(n) and String equals method takes O(n).Therefore below code will give O(n) complexity.

`public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    System.out.println("Enter a string:");
    String s = in.nextLine();
    String reverse = new StringBuilder(s).reverse().toString();
    if(s.equals(reverse)){
        System.out.println(s " is a palindrome");
    }
    else {
        System.out.println(s " is not a palindrome");
    }
}`

CodePudding user response：

Your program is already running at O(N) time!