Detect palindrome in string

Question

Given string, detect all occurrences of the palindrome pattern.

Codemia · Accepted Answer

To detect all occurrences of palindrome patterns in a string, we can identify that this problem can be effectively solved using the **two pointers technique**. This technique is applicable here because a palindrome reads the same forwards and backwards, which allows us to check for palindromic sequences by expanding outwards from potential centers of the palindrome. Given that palindromes can have both odd and even lengths, we need to consider each character and the spaces between characters as potential centers.

1. **Iterate through each character in the string**:
   - For each character, treat it as the center of a palindrome.
   - Additionally, for even-length palindromes, consider the gap between the current character and the next character as a second center.

2. **Expand Outwards**:
   - For each center, use two pointers (left and right) to expand outwards as long as the characters at these pointers are equal.
   - Collect the palindromic substrings found during this expansion.

3. **Return Results**:
   - Collect all unique palindromic substrings and return them as the final result.

**Example**: For the input string 'ababa', we will find:
   - Center at index 0: (expand from 'a') -> 'a'
   - Center at index 1: (expand from 'b') -> 'b', then 'aba'
   - Center at index 2: (expand from 'a') -> 'a', then 'bab'
   - Center at index 3: (expand from 'b') -> 'b', then 'aba'
   - Center at index 4: (expand from 'a') -> 'a'

The palindromes detected would be: ['a', 'aba', 'b', 'bab'].

```python
def find_palindromes(s):
    def expand_around_center(left, right):
        results = []
        while left >= 0 and right < len(s) and s[left] == s[right]:
            results.append(s[left:right + 1])
            left -= 1
            right += 1
        return results

palindromes = []
    for i in range(len(s)):
        # Odd length palindromes
        palindromes.extend(expand_around_center(i, i))
        # Even length palindromes
        palindromes.extend(expand_around_center(i, i + 1))

return list(set(palindromes))  # return unique palindromes
```
This function iterates through each character in the string, expanding around each character and between characters to find all palindromic substrings.

The time complexity of this approach is **O(n^2)**, where n is the length of the string. This is because for each character (n iterations), we may expand up to n/2 times in the worst-case scenario (when we find a palindrome stretching across the entire string). The space complexity is **O(n)** due to the storage of the palindromic substrings in a list, although the final returned list will be made unique, potentially reducing its size.

1. **Empty String**: Input: '' should return an empty list [].
2. **Single Character**: Input: 'a' should return ['a'] since a single character is a palindrome.
3. **No Palindromes**: Input: 'abc' should return an empty list [] since there are no palindromic patterns.
4. **All Same Characters**: Input: 'aaaa' should return ['a', 'aa', 'aaa', 'aaaa'] as all substrings are palindromic.

Detect palindrome in string

Snapchat

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Snapchat Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string