Longest Palindromic Substring in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the maximum length of palindrome found so far.

DSA Java

int maxLength = [1];

Drag options to blanks, or click blank then click option'

A0

B1

C-1

Ds.length()

Attempts:

3 left

💡 Hint

Common Mistakes

Setting maxLength to 1 initially, which assumes a palindrome exists before checking.

Using negative values which are invalid for length.

We start with maxLength = 0 because initially no palindrome substring is found.

2fill in blank

medium

Complete the code to expand around the center and return the length of palindrome.

DSA Java

while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
    left--;
    right++;
}
return [1] - [2] - 1;

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cright + 1

Dleft - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using right - left without subtracting 1, resulting in off-by-one error.

Using left - right which gives negative length.

After the loop, left and right are one step beyond the palindrome bounds, so length is right - left - 1.

3fill in blank

hard

Fix the error in the code to update the start index of the longest palindrome substring.

DSA Java

if (len > maxLength) {
    start = [1];
    maxLength = len;
}

Drag options to blanks, or click blank then click option'

Ai - len / 2

Bi - (len - 1) / 2

Ci + (len - 1) / 2

Di + len / 2

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction for start index.

Not subtracting 1 before division causing incorrect start.

The start index is calculated by moving left from center i by half the palindrome length minus one.

4fill in blank

hard

Fill both blanks to correctly find the longest palindrome by expanding around centers.

DSA Java

for (int i = 0; i < s.length(); i++) {
    int len1 = expandAroundCenter(s, i, i);
    int len2 = expandAroundCenter(s, i, [1]);
    int len = Math.max(len1, [2]);
    if (len > maxLength) {
        start = i - (len - 1) / 2;
        maxLength = len;
    }
}

Drag options to blanks, or click blank then click option'

Ai + 1

Blen1

Clen2

Di - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using i - 1 instead of i + 1 for even length center.

Using len1 instead of len2 in Math.max causing wrong length.

We check both odd length (i, i) and even length (i, i+1) palindromes and take the max length.

5fill in blank

hard

Fill all three blanks to return the longest palindromic substring from the input string.

DSA Java

return s.[1](start, start + [2]);

Drag options to blanks, or click blank then click option'

Asubstring

BmaxLength

Clength

DindexOf

Attempts:

3 left

💡 Hint

Common Mistakes

Using length or indexOf instead of maxLength for substring end.

Using indexOf which returns an integer, not a substring.

We use substring(start, start + maxLength) to extract the longest palindrome substring.

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