**I just announced the new *** Learn Spring * course, focused on the fundamentals of Spring 5 and Spring Boot 2:

*Learn Spring*course, focused on the fundamentals of Spring 5 and Spring Boot 2:

**>> CHECK OUT THE COURSE**

Last modified: September 16, 2019

In this quick tutorial, we’ll go through different approaches to **finding all substrings within a given string that are palindromes**. We'll also note the time complexity of each approach.

In this approach, we'll simply iterate over the input string to find all the substrings. At the same time, we'll check whether the substring is a palindrome or not:

```
public Set<String> findAllPalindromesUsingBruteForceApproach(String input) {
Set<String> palindromes = new HashSet<>();
for (int i = 0; i < input.length(); i++) {
for (int j = i + 1; j <= input.length(); j++) {
if (isPalindrome(input.substring(i, j))) {
palindromes.add(input.substring(i, j));
}
}
}
return palindromes;
}
```

In the example above, we just compare the substring to its reverse to see if it's a palindrome:

```
private boolean isPalindrome(String input) {
StringBuilder plain = new StringBuilder(input);
StringBuilder reverse = plain.reverse();
return (reverse.toString()).equals(input);
}
```

Of course, we can easily choose from several other approaches.

**The time complexity of this approach is O(n^3).** While this may be acceptable for small input strings, we'll need a more efficient approach if we're checking for palindromes in large volumes of text.

The idea in the centralization approach is to **consider each character as the pivot and expand in both directions to find palindromes**.

We'll only expand if the characters on the left and right side match, qualifying the string to be a palindrome. Otherwise, we continue to the next character.

Let's see a quick demonstration wherein we'll consider each character as the center of a palindrome:

```
public Set<String> findAllPalindromesUsingCenter(String input) {
Set<String> palindromes = new HashSet<>();
for (int i = 0; i < input.length(); i++) {
palindromes.addAll(findPalindromes(input, i, i + 1));
palindromes.addAll(findPalindromes(input, i, i));
}
return palindromes;
}
```

Within the loop above, we expand in both directions to get the set of all palindromes centered at each position. We'll find both even and odd length palindromes by calling the method *findPalindromes *twice in the loop*:*

```
private Set<String> findPalindromes(String input, int low, int high) {
Set<String> result = new HashSet<>();
while (low >= 0 && high < input.length() && input.charAt(low) == input.charAt(high)) {
result.add(input.substring(low, high + 1));
low--;
high++;
}
return result;
}
```

**The time complexity of this approach is O(n^2).** This is an improvement over our brute-force approach, but we can do even better, as we'll see in the next section.

**Manacher’s algorithm** **finds the longest palindromic substring in linear time**. We'll use this algorithm to find all substrings that are palindromes.

Before we dive into the algorithm, we'll initialize a few variables.

First, we'll guard the input string with a boundary character at the beginning and end before converting the resulting string to a character array:

```
String formattedInput = "@" + input + "#";
char inputCharArr[] = formattedInput.toCharArray();
```

Then, we'll use a two-dimensional array *radius* with two rows — one to store the lengths of odd-length palindromes, and the other to store lengths of even-length palindromes:

`int radius[][] = new int[2][input.length() + 1];`

Next, we'll iterate over the input array to find the length of the palindrome centered at position *i *and store this length in* radius[][]*:

```
Set<String> palindromes = new HashSet<>();
int max;
for (int j = 0; j <= 1; j++) {
radius[j][0] = max = 0;
int i = 1;
while (i <= input.length()) {
palindromes.add(Character.toString(inputCharArr[i]));
while (inputCharArr[i - max - 1] == inputCharArr[i + j + max])
max++;
radius[j][i] = max;
int k = 1;
while ((radius[j][i - k] != max - k) && (k < max)) {
radius[j][i + k] = Math.min(radius[j][i - k], max - k);
k++;
}
max = Math.max(max - k, 0);
i += k;
}
}
```

Finally, we'll traverse through the array *radius[][] *to calculate the palindromic substrings centered at each position:

```
for (int i = 1; i <= input.length(); i++) {
for (int j = 0; j <= 1; j++) {
for (max = radius[j][i]; max > 0; max--) {
palindromes.add(input.substring(i - max - 1, max + j + i - 1));
}
}
}
```

**The time complexity of this approach is O(n).**

In this quick article, we discussed the time complexities of different approaches to finding substrings that are palindromes.

As always, the full source code of the examples is available over on GitHub.

2 Comments

Oldest