Watch 4 video solutions for Check if DFS Strings Are Palindromes, a hard level problem involving Array, Hash Table, String. This walkthrough by Samad Amir has 938 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
y of x in increasing order of their numbers, and call dfs(y).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:
dfsStr and call dfs(i).dfsStr is a palindrome, then set answer[i] to true. Otherwise, set answer[i] to false.Return the array answer.
Example 1:
Input: parent = [-1,0,0,1,1,2], s = "aababa"
Output: [true,true,false,true,true,true]
Explanation:
dfs(0) results in the string dfsStr = "abaaba", which is a palindrome.dfs(1) results in the string dfsStr = "aba", which is a palindrome.dfs(2) results in the string dfsStr = "ab", which is not a palindrome.dfs(3) results in the string dfsStr = "a", which is a palindrome.dfs(4) results in the string dfsStr = "b", which is a palindrome.dfs(5) results in the string dfsStr = "a", which is a palindrome.Example 2:
Input: parent = [-1,0,0,0,0], s = "aabcb"
Output: [true,true,true,true,true]
Explanation:
Every call on dfs(x) results in a palindrome string.
Constraints:
n == parent.length == s.length1 <= n <= 1050 <= parent[i] <= n - 1 for all i >= 1.parent[0] == -1parent represents a valid tree.s consists only of lowercase English letters.Problem Overview: You are given a rooted tree and a character assigned to each node. If you run a depth‑first search starting from any node and record the characters of nodes in its subtree in DFS order, you get a string. The task is to determine for every node whether this DFS string forms a palindrome.
The challenge is that subtree DFS strings can be large. Rebuilding the string for every node leads to repeated work. Efficient solutions reuse traversal order information and use hashing to check palindrome properties quickly.
Approach 1: DFS with Inline String Building (O(n²) time, O(n) space)
This straightforward approach performs a depth-first search starting from each node and constructs the DFS string for that subtree directly. During traversal, append the node's character to a temporary string or buffer. After the traversal finishes, check whether the resulting string is a palindrome using a two‑pointer scan from both ends.
The idea is simple but expensive. Many subtrees overlap, so the same nodes are visited repeatedly. If the tree is skewed, each DFS may traverse almost the entire structure. That pushes the total complexity to O(n²). This approach is mainly useful for understanding the problem or validating smaller inputs.
Approach 2: DFS with Adjacency List + Hashing (O(n) time, O(n) space)
The optimized method builds the tree using an adjacency list and performs a single DFS traversal. While traversing, record nodes in DFS order and compute rolling hashes for the generated sequence as well as its reverse. Subtree boundaries can be tracked using entry and exit indices during the DFS.
Once each subtree corresponds to a contiguous segment of the DFS order array, palindrome checks reduce to comparing forward and reverse hash values for that segment. Hash lookups are constant time using precomputed prefix hashes and powers. This avoids reconstructing strings entirely.
This solution combines tree traversal with a hash table style rolling hash technique. Because each node is processed once and each palindrome query is O(1), the overall complexity becomes linear.
Recommended for interviews: Start by explaining the brute force DFS string construction to demonstrate understanding of subtree traversal. Then move to the optimized hashing approach. Interviewers typically expect the single‑DFS solution because it eliminates repeated traversals and scales to large trees with O(n) processing.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Inline String Building | O(n²) | O(n) | Useful for understanding the problem or when constraints are small |
| DFS with Adjacency List + Rolling Hash | O(n) | O(n) | Best general solution for large trees and interview settings |