Longest Palindromic Substring in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of longest palindromic substring length

What is the output of the following Java code that finds the length of the longest palindromic substring in the input string?

DSA Java

public class Solution {
    public static int longestPalindromeLength(String s) {
        int maxLen = 1;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            // Odd length palindrome
            int left = i, right = i;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                maxLen = Math.max(maxLen, right - left + 1);
                left--;
                right++;
            }
            // Even length palindrome
            left = i;
            right = i + 1;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                maxLen = Math.max(maxLen, right - left + 1);
                left--;
                right++;
            }
        }
        return maxLen;
    }

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

A 4

B 2

C 3

D 5

💡 Hint

Check palindromes centered at each character and between characters.

The longest palindromic substring in "babad" is "bab" or "aba", both length 3.

❓ Predict Output

intermediate

Output of longest palindromic substring for even length palindrome

What is the output of the following Java code when the input string is "cbbd"?

DSA Java

public class Solution {
    public static int longestPalindromeLength(String s) {
        int maxLen = 1;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            int left = i, right = i;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                maxLen = Math.max(maxLen, right - left + 1);
                left--;
                right++;
            }
            left = i;
            right = i + 1;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                maxLen = Math.max(maxLen, right - left + 1);
                left--;
                right++;
            }
        }
        return maxLen;
    }

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

A 1

B 3

C 4

D 2

💡 Hint

Look for even length palindromes.

The longest palindromic substring in "cbbd" is "bb", length 2.

🧠 Conceptual

advanced

Time complexity of longest palindromic substring algorithm

What is the time complexity of the standard expand-around-center approach to find the longest palindromic substring in a string of length n?

A O(n^2)

B O(n^3)

C O(n log n)

D O(n)

💡 Hint

Consider that for each center, expansion can take up to n steps.

For each of the n centers (characters and gaps), expanding can take up to n steps, resulting in O(n^2) time.

🔧 Debug

advanced

Identify the bug in longest palindromic substring code

What error will the following Java code produce when run with input "abc"?

DSA Java

public class Solution {
    public static int longestPalindromeLength(String s) {
        int maxLen = 0;
        int n = s.length();
        for (int i = 0; i <= n; i++) {
            int left = i, right = i;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                maxLen = Math.max(maxLen, right - left + 1);
                left--;
                right++;
            }
            left = i;
            right = i + 1;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                maxLen = Math.max(maxLen, right - left + 1);
                left--;
                right++;
            }
        }
        return maxLen;
    }

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

A Returns 1

B StringIndexOutOfBoundsException

C Returns 0

D Compilation error

💡 Hint

Check the loop boundary conditions carefully.

The for loop runs with i <= n, so s.charAt(i) will cause StringIndexOutOfBoundsException when i == n.

🚀 Application

expert

Longest palindromic substring in a large string

Given a string of length 100000 consisting of only 'a' and 'b', what is the length of the longest palindromic substring if the string is "a" repeated 50000 times followed by "b" repeated 50000 times?

A 50000

B 100000

C 1

D 99999

💡 Hint

Consider the longest palindrome in each uniform segment.

The longest palindrome is the entire block of 'a's or 'b's, each length 50000.

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