Palindrome Partitioning IV - Practice Coding Problems

Palindrome Partitioning IV - Problem

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

Input & Output

Example 1 — Valid 3-Way Split

$ Input: s = "abcba"

› Output: true

💡 Note: We can split "abcba" into "a" + "bcb" + "a". All three parts are palindromes: "a" is palindrome, "bcb" is palindrome, "a" is palindrome.

Example 2 — No Valid Split

$ Input: s = "abc"

› Output: false

💡 Note: No matter how we split "abc" into 3 non-empty parts, we cannot make all parts palindromes. For example: "a" + "b" + "c" - all single chars are palindromes but this works. Wait, let me recalculate: "a"|"b"|"c" are all palindromes, so this should be true. Let me use a different example.

Example 2 — No Valid Split

$ Input: s = "abcd"

› Output: false

💡 Note: No matter how we split "abcd" into 3 parts, at least one part won't be a palindrome. For instance: "a"|"b"|"cd" - "cd" is not palindrome, "a"|"bc"|"d" - "bc" is not palindrome.

Example 3 — Minimum Length

$ Input: s = "aaa"

› Output: true

💡 Note: We can split "aaa" into "a" + "a" + "a". All three single character parts are palindromes.

Constraints

3 ≤ s.length ≤ 2000
s consists of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String that needs to be split into 3 palindromic parts

Process

Try different cut positions and verify palindromes

Output

Return true if valid 3-way partition exists

Key Takeaway

🎯 Key Insight: Precompute palindrome information to efficiently check all possible 3-way partitions without redundant string comparisons

Asked in

f Facebook 25 G Google 20 M Microsoft 15

The key insight is to precompute palindrome information to avoid redundant checks. The optimal approach uses dynamic programming to build a palindrome table in O(n²) time, then checks all possible 3-way partitions efficiently. Best approach: DP with precomputation. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Two-Pass Approach	O(n²)	O(n)	Check palindromes from both ends toward center for early termination
Brute Force - Try All Partitions	O(n³)	O(1)	Try every possible way to split string into 3 parts and check palindromes
Dynamic Programming with Precomputation	O(n²)	O(n²)	Precompute palindrome table, then check all valid 3-way partitions

Optimized Two-Pass Approach — Algorithm Steps

Precompute palindromes from start
Precompute palindromes from end
Check overlapping regions for middle palindrome

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Prefixes

Find which prefixes are palindromes

Check Suffixes

Find which suffixes are palindromes

Match Middle

For valid prefix+suffix, check middle part

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

bool isPalindrome(char* s, int start, int end) {
    while (start < end) {
        if (s[start] != s[end]) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

bool solution(char* s) {
    int n = strlen(s);
    if (n < 3) return false;
    
    // Check which prefixes are palindromes
    bool* prefixPal = (bool*)malloc(n * sizeof(bool));
    for (int i = 0; i < n; i++) {
        prefixPal[i] = isPalindrome(s, 0, i);
    }
    
    // Check which suffixes are palindromes
    bool* suffixPal = (bool*)malloc(n * sizeof(bool));
    for (int i = 0; i < n; i++) {
        suffixPal[i] = isPalindrome(s, i, n - 1);
    }
    
    // Try all possible middle parts
    bool found = false;
    for (int i = 1; i < n - 1 && !found; i++) {
        if (prefixPal[i - 1]) {  // First part [0..i-1] is palindrome
            for (int j = i + 1; j < n && !found; j++) {
                if (suffixPal[j]) {  // Third part [j..n-1] is palindrome
                    if (isPalindrome(s, i, j - 1)) {  // Check middle part
                        found = true;
                    }
                }
            }
        }
    }
    
    free(prefixPal);
    free(suffixPal);
    return found;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    bool result = solution(s);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Three passes over string, each O(n²) for palindrome checking

⚠ Quadratic Growth

Space Complexity

O(n)

Two boolean arrays of size n for prefix and suffix palindromes

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Two-Pass Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler