Skip to main content

Palindromic Substrings

Question​

What is the most efficient algorithm for finding the number of palindromic substrings in a given string?

Example 1
Input: "abc"

Output: ["a", "b", "c", "a", "b", "c", "b", "ba", "cb", "bac"]

Solution​

all//Palindromic Substrings.py


def palindromic_substrings(string):
    substrings = []
    for i in range(len(string)):
        for j in range(i, len(string)):
            substring = string[i:j + 1]
            if substring == substring[::-1]:
                substrings.append(substring)
    return substrings

# example
string = "abcba"
print(palindromic_substrings(string))

# Output:
# ['a', 'b', 'c', 'b', 'a', 'bcb', 'abcba']