Teaching Kids Programming – All Odd Palindrome Substrings

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a string s, return whether all its palindromic substrings have odd lengths.

Constraints
n ≤ 100,000 where n is the length of s
Example 1
Input
s = “bab”
Output
True

Example 2
Input
s = “aa”
Output
False

Hints:
think of the necessary requirement for the even palindromic substring present in a string
What property is common across all even length palindromes?
Think of the smallest even length palindromic substring.

Odd Palindrome Substrings Algorithms

We can bruteforce, in O(N^2) quadratic time to check each substring: if it is even size, and if it is a palindrome:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def hasOddPalindromes(self, s):
        def isPalindrome(i, j):
            while i <= j and s[i] == s[j]:
                i += 1
                j -= 1
            return i > j
        n = len(s)
        for i in range(n):
            for j in range(i + 1, n, 2):
                if isPalindrome(i, j):
                    return False
        return True

class Solution:
    def hasOddPalindromes(self, s):
        def isPalindrome(i, j):
            while i <= j and s[i] == s[j]:
                i += 1
                j -= 1
            return i > j
        n = len(s)
        for i in range(n):
            for j in range(i + 1, n, 2):
                if isPalindrome(i, j):
                    return False
        return True

The time complexity is O(N^3) as O(N^2) for substrings and O(N) for check if palindrome. The space complexity is O(1).

The even size of palindromes must have two consecutive same characters. Then the problem becomes easier by checking so.

1
2
3
4
5
6

class Solution:
    def hasOddPalindromes(self, s):
        for i in range(len(s) - 1):
            if s[i] == s[i + 1]:
                return False
        return True

class Solution:
    def hasOddPalindromes(self, s):
        for i in range(len(s) - 1):
            if s[i] == s[i + 1]:
                return False
        return True

Time complexity O(N) – and space complexity is O(1). We can use Pythonic way (One-Liner):

1
2
3

class Solution:
    def hasOddPalindromes(self, s):
        return all(s[i] != s[i + 1] for i in range(len(s) - 1))

class Solution:
    def hasOddPalindromes(self, s):
        return all(s[i] != s[i + 1] for i in range(len(s) - 1))

–EOF (The Ultimate Computing & Technology Blog) —