1745. Palindrome Partitioning IV LeetCode Solution

Last updated: February 24, 2025

In this guide, you will get 1745. Palindrome Partitioning IV LeetCode Solution with the best time and space complexity. The solution to Palindrome Partitioning IV problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Palindrome Partitioning IV solution in C++
Palindrome Partitioning IV solution in Java
Palindrome Partitioning IV solution in Python
Additional Resources

1745. Palindrome Partitioning IV LeetCode Solution image

Problem Statement of Palindrome Partitioning IV

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 the same string when reversed.

Example 1:

Input: s = “abcbdd”
Output: true
Explanation: “abcbdd” = “a” + “bcb” + “dd”, and all three substrings are palindromes.

Example 2:

Input: s = “bcbddxy”
Output: false
Explanation: s cannot be split into 3 palindromes.

Constraints:

3 <= s.length <= 2000
s consists only of lowercase English letters.

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n^2)

1745. Palindrome Partitioning IV LeetCode Solution in C++

class Solution {
 public:
  bool checkPartitioning(string s) {
    const int n = s.length();
    vector<vector<int>> mem(n, vector<int>(n, -1));

    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j + 1 < n; ++j)
        if (isPalindrome(s, 0, i, mem) &&      //
            isPalindrome(s, i + 1, j, mem) &&  //
            isPalindrome(s, j + 1, n - 1, mem))
          return true;

    return false;
  }

 private:
  // Returns true if s[i..j] is a palindrome.
  // Returns false if s[i..j] is not a palindrome.
  bool isPalindrome(const string& s, int i, int j, vector<vector<int>>& mem) {
    if (i > j)
      return true;
    if (mem[i][j] != -1)
      return mem[i][j];
    if (s[i] == s[j])
      return mem[i][j] = isPalindrome(s, i + 1, j - 1, mem);
    return mem[i][j] = false;
  }
};
/* code provided by PROGIEZ */

1745. Palindrome Partitioning IV LeetCode Solution in Java

class Solution {
  public boolean checkPartitioning(String s) {
    final int n = s.length();
    Boolean[][] mem = new Boolean[n][n];

    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j + 1 < n; ++j)
        if (isPalindrome(s, 0, i, mem) &&     //
            isPalindrome(s, i + 1, j, mem) && //
            isPalindrome(s, j + 1, n - 1, mem))
          return true;

    return false;
  }

  // Returns true if s[i..j] is a palindrome.
  // Returns false if s[i..j] is not a palindrome.
  private boolean isPalindrome(final String s, int i, int j, Boolean[][] mem) {
    if (i > j)
      return true;
    if (mem[i][j] != null)
      return mem[i][j];
    if (s.charAt(i) == s.charAt(j))
      return mem[i][j] = isPalindrome(s, i + 1, j - 1, mem);
    return mem[i][j] = false;
  }
}
// code provided by PROGIEZ

1745. Palindrome Partitioning IV LeetCode Solution in Python

class Solution:
  def checkPartitioning(self, s: str) -> bool:
    @functools.lru_cache(None)
    def isPalindrome(i: int, j: int) -> bool:
      """Returns True if s[i..j] is a palindrome."""
      if i > j:
        return True
      if s[i] == s[j]:
        return isPalindrome(i + 1, j - 1)
      return False

    n = len(s)
    return any(isPalindrome(0, i) and
               isPalindrome(i + 1, j) and
               isPalindrome(j + 1, n - 1)
               for i in range(n)
               for j in range(i + 1, n - 1))
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents