Worst case runtime analysis of a string partitioning algorithm Give all the partitionings of  a string s such that every substring of the partition is a
  palindrome


What is the time complexity of this solution? And, how can I improve my code overall?

List&lt;List&lt;String&gt;&gt; resultLst;
ArrayList&lt;String&gt; currLst;
public List&lt;List&lt;String&gt;&gt; partition(String s) {
    resultLst = new ArrayList&lt;List&lt;String&gt;&gt;();
    currLst = new ArrayList&lt;String&gt;();
    backTrack(s,0);
    return resultLst;
}
public void backTrack(String s, int l){
    if(currLst.size()&gt;0 //the initial str could be palindrome
        &amp;&amp; l&gt;=s.length()){
            List&lt;String&gt; r = (ArrayList&lt;String&gt;) currLst.clone();
            resultLst.add(r);
    }
    for(int i=l;i&lt;s.length();i++){
        if(isPalindrome(s,l,i)){
            if(l==i)
                currLst.add(Character.toString(s.charAt(i)));
            else
                currLst.add(s.substring(l,i+1));
            backTrack(s,i+1);
            currLst.remove(currLst.size()-1);
        }
    }
}
public boolean isPalindrome(String str, int l, int r){
    if(l==r) return true;
    while(l&lt;r){
        if(str.charAt(l)!=str.charAt(r)) return false;
        l++;r--;
    }
    return true;
}
From looking at your code, I'd think it would be \$O(n^2)\$ or \$O(n^3)\$. I got this by:


backTrack() is called n times
backTrack() has a for loop, which is executed m-n times
In that for loop, isPalindrome() is called, which has the complexity of \$O(\frac{r-l}2)\$


Putting it together, I get:

$$O(\frac{n(n+1)(2n+1)}6)$$

I am not sure if I'm right; correct me if I'm wrong.

Since 1, 2, 4, and 6 are not significant, we can remove them, to get:

$$O(n^3)$$

I can't think of a better algorithm, but maybe there is one. I will concentrate on the naming of your variables, and other conventions.

Formatting

All right, time to complain about how bad your formatting is, part by part...


List&lt;List&lt;String&gt;&gt; resultLst;
ArrayList&lt;String&gt; currLst;
public List&lt;List&lt;String&gt;&gt; partition(String s) {
    resultLst = new ArrayList&lt;List&lt;String&gt;&gt;();
    currLst = new ArrayList&lt;String&gt;();
    backTrack(s,0);
    return resultLst;
}
public void backTrack(String s, int l){
    if(currLst.size()&gt;0 //the initial str could be palindrome
        &amp;&amp; l&gt;=s.length()){
            List&lt;String&gt; r = (ArrayList&lt;String&gt;) currLst.clone();
            resultLst.add(r);
    }
    for(int i=l;i&lt;s.length();i++){
        if(isPalindrome(s,l,i)){
            if(l==i)
                currLst.add(Character.toString(s.charAt(i)));
            else
                currLst.add(s.substring(l,i+1));
            backTrack(s,i+1);
            currLst.remove(currLst.size()-1);
        }
    }
}
public boolean isPalindrome(String str, int l, int r){
    if(l==r) return true;
    while(l&lt;r){
        if(str.charAt(l)!=str.charAt(r)) return false;
        l++;r--;
    }
    return true;
}



First of all, extra newline between methods. This allows easier readability.

Now, to the first section:

List&lt;List&lt;String&gt;&gt; resultLst;
ArrayList&lt;String&gt; currLst;

public List&lt;List&lt;String&gt;&gt; partition(String s) {
    resultLst = new ArrayList&lt;List&lt;String&gt;&gt;();
    currLst = new ArrayList&lt;String&gt;();
    backTrack(s,0); // Line 7
    return resultLst;
}


My suggestions:

Line 7: Space after comma

Well.. that was easy. Next...

public void backTrack(String s, int l){
    if(currLst.size()&gt;0 //the initial str could be palindrome
        &amp;&amp; l&gt;=s.length()){
            List&lt;String&gt; r = (ArrayList&lt;String&gt;) currLst.clone();
            resultLst.add(r);
    }
    for(int i=l;i&lt;s.length();i++){ // Line 7
        if(isPalindrome(s,l,i)){
            if(l==i)
                currLst.add(Character.toString(s.charAt(i)));
            else
                currLst.add(s.substring(l,i+1));
            backTrack(s,i+1);
            currLst.remove(currLst.size()-1);
        }
    }
}


Line 1: Space before brace

Line 2: Space after if
Line 2: Space before and after &gt;, or any other operator, for that matter
Line 2: Usually, though optional, there is a space after // in end-of-line comments

Line 3: It is recommended to use two tabs, or 8 spaces, for a continued line.
Line 3: Again, space before and after all operators.

Line 4-5: Here, it should be 4 spaced.

Line 7: Space after for
Line 7: Space before and after operators, twice
Line 7: Space after semicolons
Line 7: Space before brace

Line 8: Space after if
Line 8: Space before brace
Line 8: Space after commas

Line 9: Space after if
Line 9: Space before and after operators
Line 9: ALWAYS put braced for if statements. I explain it here.

Line 11: Again, ALWAYS put braced for if statements, including else.
Line 11: Space after comma
Line 11: Space before and after operators

Line 12: Space before and after operators
Line 12: Space after comma

Line 13: Space before and after operators
Line 13: Space after comma

Line 14: Space before and after operators

Now that was quite a bit. Notice that most of my suggestions appear over and over and over again.

Next...

public boolean isPalindrome(String str, int l, int r){
    if(l==r) return true;
    while(l&lt;r){
        if(str.charAt(l)!=str.charAt(r)) return false;
        l++;r--;
    }
    return true;
}


Line 1: Space before brace (hey, I just realised it rhymes!)

Line 2: Space after if
Line 2: Space before and after operators
Line 2: Here, I do see a reason why you made it a one-liner. I would usually not do so, but I wouldn't complain if I saw it.

Line 3: Space after while
Line 3: Space before and after operators
Line 3: Space before brace

Line 4: Space after if
Line 4: Space before and after operators
Line 4: Again, I do see a reason why you made it a one-liner. 

Line 5: Separate into two lines. I would never put two statements on one line, no matter how related.

Done! Result after formatting:

List&lt;List&lt;String&gt;&gt; resultLst;
ArrayList&lt;String&gt; currLst;

public List&lt;List&lt;String&gt;&gt; partition(String s) {
    resultLst = new ArrayList&lt;List&lt;String&gt;&gt;();
    currLst = new ArrayList&lt;String&gt;();
    backTrack(s, 0);
    return resultLst;
}

public void backTrack(String s, int l) {
    if (currLst.size() &gt; 0 // the initial str could be palindrome
            &amp;&amp; l &gt;= s.length()) {
        List&lt;String&gt; r = (ArrayList&lt;String&gt;) currLst.clone();
        resultLst.add(r);
    }
    for (int i = l; i &lt; s.length(); i++) {
        if (isPalindrome(s, l, i)) {
            if (l == i) {
                currLst.add(Character.toString(s.charAt(i)));
            } else {
                currLst.add(s.substring(l, i + 1));
            }
            backTrack(s, i + 1);
            currLst.remove(currLst.size() - 1);
        }
    }
}

public boolean isPalindrome(String str, int l, int r) {
    if (l == r) return true;
    while (l &lt; r) {
        if (str.charAt(l) != str.charAt(r)) return false;
        l++;
        r--;
    }
    return true;
}


Naming

Most of your variable names are not exactly good. Names say what the variable is for, and is not just there to identify a from b. I would suggest:


resultLst -> result
currLst -> currentList
resultLst -> result


In partition():


s -> string or toPartition


In backtrack():


s -> string or toPartition
l -> len or length
r -> list or toAdd


In isPalindrome():


str -> string
l -> from
r -> to


Result:

List&lt;List&lt;String&gt;&gt; result;
ArrayList&lt;String&gt; currentList;

public List&lt;List&lt;String&gt;&gt; partition(String string) {
    result = new ArrayList&lt;List&lt;String&gt;&gt;();
    currentList = new ArrayList&lt;String&gt;();
    backTrack(string, 0);
    return result;
}

public void backTrack(String string, int length) {
    if (currentList.size() &gt; 0 // the initial str could be palindrome
            &amp;&amp; length &gt;= string.length()) {
        List&lt;String&gt; list = (ArrayList&lt;String&gt;) currentList.clone();
        result.add(list);
    }
    for (int i = length; i &lt; string.length(); i++) {
        if (isPalindrome(string, length, i)) {
            if (length == i) {
                currentList.add(Character.toString(string.charAt(i)));
            } else {
                currentList.add(s.substring(length, i + 1));
            }
            backTrack(string, i + 1);
            currentList.remove(currentList.size() - 1);
        }
    }
}

public boolean isPalindrome(String string, int from, int to) {
    if (from == to) return true;
    while (from &lt; to) {
        if (string.charAt(from) != string.charAt(to)) return false;
        from++;
        to--;
    }
    return true;
}


Misc


Declare all lists at List&lt;Type&gt;
result and currentList should be private