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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Palindrome Partitioning IV

Number: 1871

Difficulty: Hard

Paid? No

Companies: tcs

Problem Description

Given a string s, return true if it is possible to split s into three non-empty palindromic substrings. A substring is a palindrome if it reads the same forwards and backwards.

Key Insights

  • We need to split the string into exactly three parts where each part is a palindrome.
  • Precomputing palindromic substrings using dynamic programming allows us to check any substring in constant time after an O(n²) preprocessing.
  • Iterate over possible split points for the first and second cut while checking the precomputed DP table to verify each substring is a palindrome.

Space and Time Complexity

Time Complexity: O(n²) due to the DP precomputation of all palindromic substrings. Space Complexity: O(n²) because of the DP table used to store palindrome status for each substring.

Solution

We use a dynamic programming approach to precompute a 2D boolean table dp where dp[i][j] is true if the substring s[i...j] is a palindrome. To fill this table:

  • Every single character is a palindrome.
  • For substrings of length 2 or more, a substring is a palindrome if its endpoints match and the inner substring is a palindrome. Once the table is built, we iterate through potential split indices i and j (with 0 < i < j < n) to ensure: • The substring s[0...i-1] is a palindrome. • The substring s[i...j-1] is a palindrome. • The substring s[j...n-1] is a palindrome. The existence of such a split implies a valid partition, and we return true if found.

Code Solutions

def isThreePalindromes(s):
    n = len(s)
    # Create a DP table: dp[i][j] is True if s[i:j+1] is a palindrome.
    dp = [[False] * n for _ in range(n)]
    
    # Every single character is a palindrome.
    for i in range(n):
        dp[i][i] = True

    # Fill the table for substrings of length 2 and more.
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1   # Ending index of the substring.
            if s[i] == s[j]:
                dp[i][j] = (length == 2) or dp[i + 1][j - 1]
    
    # Try every split where:
    # First part: s[0:i], Second part: s[i:j], Third part: s[j:n]
    for i in range(1, n - 1):
        if dp[0][i - 1]:
            for j in range(i + 1, n):
                if dp[i][j - 1] and dp[j][n - 1]:
                    return True
    return False

# Example Usage
s1 = "abcbdd"
print(isThreePalindromes(s1))  # Expected output: True

s2 = "bcbddxy"
print(isThreePalindromes(s2))  # Expected output: False
← Back to All Questions