-1

Here I wrote a program that will print longest palindromic substring in a given string.. Here can you suggest me how to improve performance of this program..

void longestPalindrome(){

    String str = "malayalam";
    String pal = "";
    int c = 0;
    String arr[] = new String[100];
    for(int i=0;i<str.length();i++){
        for(int j=i;j<str.length();j++){
            if(str.charAt(i)==str.charAt(j)){
                pal = str.substring(i,j+1);
                if(pal.length()>2 && checkPalindrome(pal)){
                    System.out.println(pal);
                    arr[c] = pal;
                    c=c+1;
                }
                pal = "";
            }
        }
    }
    String newArray[] = new String[c];
    System.out.print("The Palindromes are!!-->>>");
    for(int k=0;k<c;k++){
        newArray[k] = arr[k];
        System.out.print(newArray[k]+",");
    }
    System.out.println();
    if(newArray.length>1){
    for(int i=0;i<newArray.length;i++){
        for(int j=i+1;j<newArray.length;j++)
            if(newArray[i].length() < newArray[j].length()){
                String temp = newArray[i];
                newArray[i] = newArray[j];
                newArray[j] = temp;
            }
    }
    }
    if(newArray.length>0)
        System.out.println("The LONGEST PALINDROME --- "+newArray[0]);
Balaji
  • 1,773
  • 1
  • 17
  • 30
  • Open-ended questions about performance improvements are considered off-topic for stack overflow. Please consider posting on [Code Review](https://codereview.stackexchange.com). See [How Do I Ask a Good Question?](https://codereview.stackexchange.com/help/how-to-ask) before posting there. – Michael Feb 11 '19 at 08:20

1 Answers1

0

The big O notation is a metric for complexity and you want to keep it as low as possible. O(n) is linear complexity and is good O(n^2) is polynomial and is worse than O(n) but it can be good or bad depending on the problem.

n is the size of the input parameter. In your problem n is the number of characters of the input String. You are are using a nested loop for the size of n. Therefore the inner loop will execute n^2 times and your complexity is O(n^2). Keep in mind that having two n loops next to each other give complexity O(2*n)=O(n).

To decrease the complexity you will have to produce non nested loops in your solution. I am not sure what happens in your code, seems that some copy-paste went wrong. Also, I am not sure about all the restrictions of your problem.

Dimitris
  • 560
  • 3
  • 17