Print all palindromic substrings

Sample i/p = abcc

Sample o/p = a, b, c, cc, c

package jan25;

public class Palindrome {
    public static void main(String[] args) {

        String str = "abcc";
        int n = str.length();

        // Time Complexity: O(n^3)
        // - Outer loop runs O(n)
        // - Inner loop runs up to O(n) for each i
        // - Substring + palindrome check takes O(n) time in worst case
        //
        // Space Complexity: O(n)
        // - For temporary substring storage, O(n) space in worst case
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String temp = str.substring(i, j + 1); // O(n) in worst case
                if (isPalindrome(temp)) {
                    System.out.println(temp);
                }
            }
        }
    }

    // Time Complexity: O(k), where k is length of the string
    // Space Complexity: O(1), constant space used
    private static boolean isPalindrome(String str) {
        int l = 0, r = str.length() - 1;

        while (l < r) {
            if (str.charAt(l++) != str.charAt(r--))
                return false;
        }

        return true;
    }
}

Summary:
Overall Time Complexity: O(n³): (due to O(n²) substring generation and O(n) palindrome check per substring)
Space Complexity: O(n): (due to creation of temporary substrings during each iteration)





Case
Time Complexity
Space Complexity
Explanation




Best
O(n²)
O(n)
All characters are unique — minimal palindromic substrings checked.


Average
O(n³)
O(n)
Moderate palindromic substrings — typical case with varying substring sizes.


Worst
O(n³)
O(n)
All substrings are palindromes — every substring checked and stored.


Notes:
n = length of input string
Substring creation and palindrome checks dominate time complexity
Temporary substring storage leads to linear space usage in worst case per iteration