Coderust: Hacking the Coding Interview/

...

/

Find all Palindrome Substrings

Find all Palindrome Substrings

Given a string, find all substrings that are palindromes.

We'll cover the following...

Statement

Given a string, find all non-single letter substrings that are palindromes.

A palindrome is a word, phrase, number, or other sequence of characters that reads the same backwards as it reads forwards.

Example

Below is an example of all possible non single-letter palindromes of string aabbbaa:

g array Input string aabbbaa array2 Palindrome substring aa bb bbb abbba aabbbaa bb aa

Sample input

Input string to find non single-letter substring.

Input string: "aabbbaa"

Expected output

The expected output of the above string will be:

Palindrome substrings: ["aa", "bb", "bbb", "abbba", "aabbbaa", "bb", "aa"]

Try it yourself

#include <iostream>
#include <string>
#include <vector>
using namespace std;
// This function receives input_string and returns palindromes list
vector<string> FindAllPalindromeSubstrings(const string& input_string) {
	//TODO: Write - Your - Code
	return {""};
}

Solution 1

A naive solution of this problem is to find all substrings of a given string and check whether each substring is a palindrome or not. This solution has a complexity of O(n3)O(n^3) ...

Access this course and 1400+ top-rated courses and projects.