We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Palindrome Partitioning IV

Difficulty: Hard

Problem Description

Given a string s, return true if it is possible to split the string s into three non-empty palindromic substrings. Otherwise, return false. A string is said to be palindrome if it is the same string when reversed.

Key Insights

  • A palindrome reads the same forwards and backwards.
  • The task involves splitting the string into exactly three non-empty parts.
  • Dynamic programming can be utilized to precompute which substrings are palindromes.
  • We can check all possible positions to split the string into three parts and verify if each part is a palindrome.

Space and Time Complexity

Time Complexity: O(n^2) - where n is the length of the string. This is due to the double loop for checking palindromic substrings. Space Complexity: O(n^2) - for storing palindrome checks in a 2D array.

Solution

To solve the problem, we can use a dynamic programming approach. We create a 2D boolean array isPalindrome where isPalindrome[i][j] indicates whether the substring s[i:j+1] is a palindrome. We then iterate through the string and check all possible ways to split it into three parts. For each split, we verify if all three parts are palindromic using the precomputed isPalindrome array.

Code Solutions

def isPalindromePartitioningPossible(s: str) -> bool:
    n = len(s)
    isPalindrome = [[False] * n for _ in range(n)]

    # Fill the palindrome table
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if length == 1:
                isPalindrome[i][j] = True
            elif length == 2:
                isPalindrome[i][j] = (s[i] == s[j])
            else:
                isPalindrome[i][j] = (s[i] == s[j]) and isPalindrome[i + 1][j - 1]

    # Check for valid partitioning
    for i in range(1, n - 1):
        for j in range(i + 1, n):
            if isPalindrome[0][i - 1] and isPalindrome[i][j - 1] and isPalindrome[j][n - 1]:
                return True
    return False
← Back to All Questions