Check if DFS Strings Are Palindromes - Practice Coding Problems

Check if DFS Strings Are Palindromes - Problem

Array Hash Table String Tree Depth-First Search Hash Function Hard

You are given a tree rooted at node 0, consisting of n nodes numbered from 0 to n - 1. The tree is represented by an array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1.

You are also given a string s of length n, where s[i] is the character assigned to node i.

Consider an empty string dfsStr, and define a recursive function dfs(int x) that takes a node x as a parameter and performs the following steps in order:

Iterate over each child y of x in increasing order of their numbers, and call dfs(y).
Add the character s[x] to the end of the string dfsStr.

Note that dfsStr is shared across all recursive calls of dfs.

You need to find a boolean array answer of size n, where for each index i from 0 to n - 1, you do the following:

Empty the string dfsStr and call dfs(i).
If the resulting string dfsStr is a palindrome, then set answer[i] to true. Otherwise, set answer[i] to false.

Return the array answer.

Input & Output

Example 1 — Basic Tree

$ Input: parent = [-1,0,0,1,1], s = "aaaab"

› Output: [true,true,true,true,true]

💡 Note: Node 0 DFS: visit 3,4,1,2,0 → "aabaa" (palindrome). Node 1 DFS: visit 3,4,1 → "aba" (palindrome). All other nodes produce single characters or palindromes.

Example 2 — Mixed Characters

$ Input: parent = [-1,0,0,1], s = "abcd"

› Output: [false,false,true,true]

💡 Note: Node 0 DFS: visit 3,1,2,0 → "dcba" (not palindrome). Node 1 DFS: visit 3,1 → "db" (not palindrome). Nodes 2,3 are single characters (palindromes).

Example 3 — Single Node

$ Input: parent = [-1], s = "a"

› Output: [true]

💡 Note: Only root node, DFS produces "a" which is a palindrome.

Constraints

n == parent.length == s.length
1 ≤ n ≤ 10⁵
parent[0] == -1
0 ≤ parent[i] ≤ n - 1 for i ≠ 0
parent represents a valid tree
s consists of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Tree Structure

Build tree from parent array with node characters

DFS Traversal

Post-order DFS: children first, then current node

Palindrome Check

Verify if DFS string reads same forwards and backwards

Key Takeaway

🎯 Key Insight: DFS creates post-order strings by visiting children first, then adding current node character

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is that DFS visits children first then adds current node, creating post-order traversal strings. Best approach uses single DFS pass with memoization to compute all subtree strings efficiently. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Precomputed Strings	O(n²)	O(n²)	Precompute DFS strings for all nodes in one traversal using post-order
Brute Force DFS	O(n²)	O(n)	For each node, build DFS string from scratch and check palindrome

Optimized with Precomputed Strings — Algorithm Steps

Build tree structure from parent array
Perform single post-order DFS to compute all subtree strings
Check palindrome for each precomputed string

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Tree

Create adjacency list from parent array

Single DFS Pass

Compute and memoize DFS strings for all nodes

Check All

Verify palindromes using precomputed strings

Code -

solution.c — C

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

#define MAX_N 1000
#define MAX_STR 1000

int children[MAX_N][MAX_N];
int childCount[MAX_N];
char dfsStrings[MAX_N][MAX_STR];

void dfs(int node, char* s, int n) {
    if (strlen(dfsStrings[node]) > 0) return;
    
    // Visit children first in increasing order
    for (int i = 0; i < childCount[node]; i++) {
        int child = children[node][i];
        dfs(child, s, n);
        strcat(dfsStrings[node], dfsStrings[child]);
    }
    
    // Add current node's character
    int len = strlen(dfsStrings[node]);
    dfsStrings[node][len] = s[node];
    dfsStrings[node][len + 1] = '\0';
}

bool isPalindrome(char* str) {
    int len = strlen(str);
    int left = 0, right = len - 1;
    while (left < right) {
        if (str[left] != str[right]) return false;
        left++;
        right--;
    }
    return true;
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

bool* solution(int* parent, int parentSize, char* s) {
    int n = parentSize;
    bool* answer = (bool*)malloc(n * sizeof(bool));
    
    // Initialize
    memset(childCount, 0, sizeof(childCount));
    memset(dfsStrings, 0, sizeof(dfsStrings));
    
    // Build adjacency list
    for (int i = 0; i < n; i++) {
        if (parent[i] != -1) {
            children[parent[i]][childCount[parent[i]]++] = i;
        }
    }
    
    // Sort children for each node
    for (int i = 0; i < n; i++) {
        qsort(children[i], childCount[i], sizeof(int), compare);
    }
    
    // Compute DFS strings and check palindromes
    for (int i = 0; i < n; i++) {
        dfs(i, s, n);
        answer[i] = isPalindrome(dfsStrings[i]);
    }
    
    return answer;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse parent array
    int parent[MAX_N];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        parent[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    char s[MAX_N];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    bool* result = solution(parent, n, s);
    
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%s", result[i] ? "true" : "false");
        if (i < n - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Single DFS traversal O(n) but string operations can be O(n) each, total O(n²)

⚠ Quadratic Growth

Space Complexity

O(n²)

Store DFS strings for all nodes, each string can be up to n characters

⚠ Quadratic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

286 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 with Precomputed Strings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler