Jobs

Interviews

Discussions

Palindromic Substrings

Medium

Asked by:

+15

33 views

Topics:

StringsDynamic Programming

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints:

1 <= s.length <= 1000
s consists of lowercase English letters.

Palindromic Substrings

Medium

Asked by:

33 views

Topics:

StringsDynamic Programming

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints:

1 <= s.length <= 1000
s consists of lowercase English letters.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string s?
Can the input string s contain non-alphanumeric characters, or is it limited to only letters and numbers?
Is case significant when determining if a substring is a palindrome (e.g., is 'Racecar' a palindrome)?
Should I include single-character substrings as palindromes?
Are there any specific constraints on memory usage or stack depth?

Brute Force Solution

Approach

The brute force approach to finding palindromic substrings is all about checking everything. We look at every possible piece of the given text, and for each piece, we check if it's a palindrome (reads the same forwards and backward). Then we count how many of these palindromic pieces we've found.

Here's how the algorithm would work step-by-step:

Consider the first character of the text all by itself. Check if it's a palindrome. It will be.
Now consider the first two characters together. Check if this small group forms a palindrome.
Then, consider the first three characters, and so on, up to the entire text. Each time, check if the group of characters is a palindrome.
Next, move on to the second character of the original text. Consider it alone, then with the character after it, then with the two characters after it, and so on, again checking for palindromes each time.
Keep repeating this process, moving the starting point one character at a time and considering all possible lengths of text fragments starting from that point.
Every time you find a piece of text that reads the same backward as forward, increase your count of palindromic substrings.
When you've checked every possible piece of the original text, the final count is the number of palindromic substrings.

Code Implementation

def count_palindromic_substrings_brute_force(input_string):
    number_of_palindromic_substrings = 0
    string_length = len(input_string)

    # Iterate over all possible start indices
    for start_index in range(string_length):

        # Iterate over all possible end indices for each start index
        for end_index in range(start_index, string_length):
            substring = input_string[start_index:end_index + 1]

            # Check if the substring is a palindrome
            if substring == substring[::-1]:

                #Increment if palindrome condition is met
                number_of_palindromic_substrings += 1

    return number_of_palindromic_substrings

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n³) – The brute force approach iterates through all possible substrings of the input string of length n. There are approximately n²/2 possible substrings. For each of these substrings, we perform a palindrome check, which takes O(n) time in the worst case (comparing up to n/2 characters). Therefore, the overall time complexity is O(n² * n), which simplifies to O(n³).

Space Complexity

O(1) – The brute force approach, as described, iterates through all possible substrings and checks if each substring is a palindrome. The only extra space needed is for a few integer variables, such as loop counters, and potentially a boolean variable to store the result of the palindrome check for a given substring. The space needed for these variables does not depend on the input string's size (N). Therefore, the auxiliary space complexity is constant, or O(1).

Optimal Solution

Approach

Instead of checking every possible substring, we can find all palindromic substrings efficiently by expanding around each character and pair of adjacent characters. This method smartly reuses previously discovered palindromes to avoid redundant checks. This 'expand from the middle' approach drastically reduces the work needed.

Here's how the algorithm would work step-by-step:

Consider each character in the string as the potential center of a palindrome.
Also consider each pair of adjacent characters as the potential center of a palindrome.
For each center, try to expand outwards, one character at a time on both sides.
If the characters on both sides are the same, then you have found a larger palindrome.
Keep expanding until you find characters that do not match or reach the beginning/end of the string.
Each time you find a new palindrome, remember to count it.
After checking all possible centers, the count of all remembered palindromes will be your answer.

Code Implementation

def count_palindromic_substrings(input_string):
    string_length = len(input_string)
    palindrome_count = 0

    for i in range(string_length):
        # Check for odd length palindromes
        left_index = i
        right_index = i

        # Expand around the center to find palindromes.
        while left_index >= 0 and right_index < string_length and input_string[left_index] == input_string[right_index]:
            palindrome_count += 1
            left_index -= 1
            right_index += 1

        # Check for even length palindromes
        left_index = i
        right_index = i + 1

        # Expand around the center to find palindromes.
        while left_index >= 0 and right_index < string_length and input_string[left_index] == input_string[right_index]:
            # Found another palindrome.
            palindrome_count += 1
            left_index -= 1
            right_index += 1

    return palindrome_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each character in the string of length n, considering it as the potential center of a palindrome. For each such center, the algorithm expands outwards until a non-palindromic sequence is encountered or the string boundaries are reached. In the worst-case scenario (e.g., a string with all identical characters), this expansion can take O(n) time for each of the n centers. Therefore, the total time complexity is proportional to n * n, simplifying to O(n²).

Space Complexity

O(1) – The provided algorithm for finding palindromic substrings operates primarily by expanding outwards from potential center points. While it counts the number of palindromes, it does so using a simple counter variable. No auxiliary data structures that scale with the input string's length N (where N is the length of the string) are used. Therefore, the space complexity is constant, O(1).

Edge Cases

Case	How to Handle
Null or Empty String Input	Return 0 if the input string is null or empty as there are no substrings.
Single Character String	A single character string is always a palindrome, so return 1.
String with all identical characters (e.g., 'aaaa')	The number of palindromic substrings should be n*(n+1)/2, handled correctly by expanding around each character.
String with alternating characters (e.g., 'abab')	The algorithm should identify palindromes like 'a', 'b', 'aba', 'bab', and 'aba'.
Very Long Input String	Ensure the solution's time complexity is optimized (e.g., O(n^2) using dynamic programming or expanding around centers) to avoid Time Limit Exceeded errors.
String contains special characters or spaces	The solution should correctly identify palindromes even with special characters or spaces.
String with only two different characters repeated multiple times (e.g., 'aabbbaa')	The algorithm needs to identify both single-character and longer palindromes formed by these repeating characters.
String with maximum length constraint	Verify there is no integer overflow when calculating string lengths or substring boundaries.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string s?
Can the input string s contain non-alphanumeric characters, or is it limited to only letters and numbers?
Is case significant when determining if a substring is a palindrome (e.g., is 'Racecar' a palindrome)?
Should I include single-character substrings as palindromes?
Are there any specific constraints on memory usage or stack depth?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider the first character of the text all by itself. Check if it's a palindrome. It will be.
Now consider the first two characters together. Check if this small group forms a palindrome.
Then, consider the first three characters, and so on, up to the entire text. Each time, check if the group of characters is a palindrome.
Next, move on to the second character of the original text. Consider it alone, then with the character after it, then with the two characters after it, and so on, again checking for palindromes each time.
Keep repeating this process, moving the starting point one character at a time and considering all possible lengths of text fragments starting from that point.
Every time you find a piece of text that reads the same backward as forward, increase your count of palindromic substrings.
When you've checked every possible piece of the original text, the final count is the number of palindromic substrings.

Code Implementation

def count_palindromic_substrings_brute_force(input_string):
    number_of_palindromic_substrings = 0
    string_length = len(input_string)

    # Iterate over all possible start indices
    for start_index in range(string_length):

        # Iterate over all possible end indices for each start index
        for end_index in range(start_index, string_length):
            substring = input_string[start_index:end_index + 1]

            # Check if the substring is a palindrome
            if substring == substring[::-1]:

                #Increment if palindrome condition is met
                number_of_palindromic_substrings += 1

    return number_of_palindromic_substrings

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Consider each character in the string as the potential center of a palindrome.
Also consider each pair of adjacent characters as the potential center of a palindrome.
For each center, try to expand outwards, one character at a time on both sides.
If the characters on both sides are the same, then you have found a larger palindrome.
Keep expanding until you find characters that do not match or reach the beginning/end of the string.
Each time you find a new palindrome, remember to count it.
After checking all possible centers, the count of all remembered palindromes will be your answer.

Code Implementation

def count_palindromic_substrings(input_string):
    string_length = len(input_string)
    palindrome_count = 0

    for i in range(string_length):
        # Check for odd length palindromes
        left_index = i
        right_index = i

        # Expand around the center to find palindromes.
        while left_index >= 0 and right_index < string_length and input_string[left_index] == input_string[right_index]:
            palindrome_count += 1
            left_index -= 1
            right_index += 1

        # Check for even length palindromes
        left_index = i
        right_index = i + 1

        # Expand around the center to find palindromes.
        while left_index >= 0 and right_index < string_length and input_string[left_index] == input_string[right_index]:
            # Found another palindrome.
            palindrome_count += 1
            left_index -= 1
            right_index += 1

    return palindrome_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or Empty String Input	Return 0 if the input string is null or empty as there are no substrings.
Single Character String	A single character string is always a palindrome, so return 1.
String with all identical characters (e.g., 'aaaa')	The number of palindromic substrings should be n*(n+1)/2, handled correctly by expanding around each character.
String with alternating characters (e.g., 'abab')	The algorithm should identify palindromes like 'a', 'b', 'aba', 'bab', and 'aba'.
Very Long Input String	Ensure the solution's time complexity is optimized (e.g., O(n^2) using dynamic programming or expanding around centers) to avoid Time Limit Exceeded errors.
String contains special characters or spaces	The solution should correctly identify palindromes even with special characters or spaces.
String with only two different characters repeated multiple times (e.g., 'aabbbaa')	The algorithm needs to identify both single-character and longer palindromes formed by these repeating characters.
String with maximum length constraint	Verify there is no integer overflow when calculating string lengths or substring boundaries.