Longest Palindromic Substring in DSA Java - Time & Space Complexity

Time Complexity: Longest Palindromic Substring

O(n²)

Understanding Time Complexity

We want to understand how the time needed to find the longest palindromic substring changes as the input string gets longer.

How does the number of steps grow when the string size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public String longestPalindrome(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    String res = "";
    for (int len = 0; len < n; len++) {
        for (int start = 0; start + len < n; start++) {
            int end = start + len;
            dp[start][end] = (s.charAt(start) == s.charAt(end)) 
                && (len < 2 || dp[start + 1][end - 1]);
            if (dp[start][end] && len + 1 > res.length()) {
                res = s.substring(start, end + 1);
            }
        }
    }
    return res;
}

This code finds the longest palindromic substring using dynamic programming by checking all possible substrings.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops checking all substrings of the input string.
• How many times: Outer loop runs n times, inner loop runs up to n times for each outer loop, so roughly n x n = n² times.

How Execution Grows With Input

As the string length grows, the number of substring checks grows roughly with the square of the length.

Input Size (n)	Approx. Operations
10	About 100 checks
100	About 10,000 checks
1000	About 1,000,000 checks

Pattern observation: Doubling the input size roughly quadruples the work because of the nested loops.

Final Time Complexity

Time Complexity: O(n²)

This means the time needed grows roughly with the square of the input string length.

Common Mistake

[X] Wrong: "Since we only check pairs of characters, the time is O(n)."

[OK] Correct: We check all substrings, not just pairs, so the number of checks grows much faster than the string length.

Interview Connect

Understanding this time complexity helps you explain how your solution scales and shows you can analyze nested loops clearly.

Self-Check

"What if we used a center expansion method instead of dynamic programming? How would the time complexity change?"

Practice

1. What is the main goal of the Longest Palindromic Substring problem?

easy

A. Find the longest substring with all unique characters

B. Find the longest substring with increasing characters

C. Find the longest substring that reads the same forwards and backwards

D. Find the longest substring that contains only vowels

Solution

1. Step 1: Understand the problem definition

   The problem asks to find a substring that is a palindrome, meaning it reads the same forwards and backwards.

2. Step 2: Identify the goal

   Among all palindromic substrings, we want the one with the maximum length.

3. Final Answer:

   Find the longest substring that reads the same forwards and backwards -> Option C

4. Quick Check:

   Longest Palindromic Substring = Find palindrome substring [OK]

Hint: Look for substring that mirrors itself [OK]

Common Mistakes:

• Confusing palindrome with unique characters
• Looking for longest substring without repeats
• Thinking about character order increasing

2. Which of the following Java method signatures is correct for a function that returns the longest palindromic substring from a given string s?

easy

A. public String longestPalindrome(String s)

B. public void longestPalindrome(String s)

C. public int longestPalindrome(String s)

D. public String longestPalindrome(int s)

Solution

1. Step 1: Analyze the return type

   The function should return the longest palindromic substring, which is a String.

2. Step 2: Check parameter type

   The input is a string, so the parameter should be of type String.

3. Final Answer:

   public String longestPalindrome(String s) -> Option A

4. Quick Check:

   Return type String and parameter String = public String longestPalindrome(String s) [OK]

Hint: Return type matches output, parameter matches input [OK]

Common Mistakes:

• Using void return type when output is needed
• Using int parameter instead of String
• Returning int instead of String

3. What will be the output of the following Java code snippet?

public class Test {
  public static String longestPalindrome(String s) {
    int start = 0, maxLen = 1;
    for (int i = 0; i < s.length(); i++) {
      for (int j = i; j < s.length(); j++) {
        String sub = s.substring(i, j + 1);
        if (isPalindrome(sub) && sub.length() > maxLen) {
          start = i;
          maxLen = sub.length();
        }
      }
    }
    return s.substring(start, start + maxLen);
  }

  private static boolean isPalindrome(String str) {
    int left = 0, right = str.length() - 1;
    while (left < right) {
      if (str.charAt(left++) != str.charAt(right--)) return false;
    }
    return true;
  }

  public static void main(String[] args) {
    System.out.println(longestPalindrome("babad"));
  }
}

medium

A. "babad"

B. "aba"

C. "bad"

D. "bab"

Solution

1. Step 1: Understand the code logic

   The code checks all substrings and updates the longest palindrome found.

2. Step 2: Trace the input "babad"

   Palindromic substrings include "bab" and "aba" both length 3. The code picks the first found longest palindrome, which is "bab".

3. Final Answer:

   "bab" -> Option D

4. Quick Check:

   First longest palindrome found = "bab" [OK]

Hint: Check first longest palindrome substring found [OK]

Common Mistakes:

• Assuming "aba" is returned instead of "bab"
• Thinking entire string is palindrome
• Ignoring substring length comparison

4. Identify the bug in the following code snippet for finding the longest palindromic substring:

public String longestPalindrome(String s) {
  int maxLen = 0, start = 0;
  for (int i = 0; i < s.length(); i++) {
    for (int j = i; j < s.length(); j++) {
      String sub = s.substring(i, j);
      if (isPalindrome(sub) && sub.length() > maxLen) {
        maxLen = sub.length();
        start = i;
      }
    }
  }
  return s.substring(start, start + maxLen);
}

medium

A. The loop should start from j = i + 1

B. The substring end index should be j + 1, not j

C. maxLen should be initialized to 1, not 0

D. The isPalindrome method is missing

Solution

1. Step 1: Check substring usage

   Java substring method excludes the end index, so substring(i, j) misses character at j.

2. Step 2: Correct substring end index

   It should be substring(i, j + 1) to include character at position j.

3. Final Answer:

   The substring end index should be j + 1, not j -> Option B

4. Quick Check:

   substring(i, j + 1) includes full substring [OK]

Hint: Remember substring excludes end index [OK]

Common Mistakes:

• Using substring(i, j) which excludes last char
• Not updating maxLen correctly
• Ignoring substring indexing rules

5. Given the string "forgeeksskeegfor", which approach will efficiently find the longest palindromic substring and what is the substring?

hard

A. Dynamic programming with memoization; longest palindrome is "geeksskeeg"

B. Brute force checking all substrings; longest palindrome is "forgeeksskeegfor"

C. Expand around center approach; longest palindrome is "sskeeg"

D. Sorting characters and checking; longest palindrome is "sskeeg"

Solution

1. Step 1: Identify efficient methods

   Dynamic programming and expand around center are efficient for this problem; brute force is slow.

2. Step 2: Check longest palindrome in given string

   "geeksskeeg" is the longest palindromic substring inside "forgeeksskeegfor".

3. Step 3: Match approach and answer

   Dynamic programming with memoization is a common efficient approach returning "geeksskeeg".

4. Final Answer:

   Dynamic programming with memoization; longest palindrome is "geeksskeeg" -> Option A

5. Quick Check:

   DP approach finds "geeksskeeg" efficiently [OK]

Hint: Use DP or center expansion for efficiency [OK]

Common Mistakes:

• Assuming entire string is palindrome
• Using brute force for large strings
• Sorting characters loses substring order