#3327

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Check if DFS Strings Are Palindromes

Determine if strings formed by DFS traversal of a tree are palindromes using array scanning and hash lookups efficiently.

array hash table string tree depth first search

Problem Statement

You are given a rooted tree with n nodes labeled from 0 to n - 1. The tree is represented by an array parent of length n, where parent[i] indicates the parent of node i, and parent[0] == -1 since node 0 is the root. Each node i has an associated lowercase letter s[i].

Define an empty string dfsStr and a recursive function dfs(int x) that appends s[x] to dfsStr and recursively visits each child of x. After each call to dfs(x), determine whether dfsStr forms a palindrome. Return an array of booleans where the ith element is true if the DFS string ending at node i is a palindrome, and false otherwise.

Examples

Example 1

Input: parent = [-1,0,0,1,1,2], s = "aababa"

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

Example 2

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

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

Every call on dfs(x) results in a palindrome string.

Constraints

n == parent.length == s.length
1 <= n <= 105
0 = 1.
parent[0] == -1
parent represents a valid tree.
s consists only of lowercase English letters.

Solution Approach

DFS Traversal with Bitmasking

Perform a DFS starting from the root and use a bitmask integer to represent character counts modulo 2. Toggle the bit corresponding to s[x] at each node. After visiting children, a palindrome is possible if the bitmask has at most one bit set, indicating at most one character has an odd count.

Array-Based Child Tracking

Precompute the children of each node into an array of lists to avoid repeated parent lookups. This allows constant-time access to all children during DFS and prevents recomputation, improving runtime efficiency on large trees.

Avoid String Reconstruction

Do not build the full DFS string for each node. Instead, maintain cumulative counts or bitmasks along the traversal. This reduces time complexity from O(n^2) to O(n) and ensures memory usage stays linear with the number of nodes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each node is visited once and child accesses are O(1). Space complexity is O(n) for storing children arrays and maintaining the bitmask or frequency counts during DFS.

What Interviewers Usually Probe

Candidate attempts naive string concatenation for each DFS call.
Candidate uses a hash or frequency map to track characters.
Candidate considers bit manipulation to optimize palindrome checking.

Common Pitfalls or Variants

Common pitfalls

Rebuilding the DFS string for every node, leading to O(n^2) time complexity.
Incorrectly handling the root node or parent array indexing.
Failing to consider that a palindrome allows at most one character with odd count.

Follow-up variants

Check if BFS strings are palindromes using a similar hash counting approach.
Verify palindrome paths in a weighted tree with additional constraints.
Determine all nodes where concatenated ancestor labels form palindromes under dynamic updates.

FAQ

What pattern does Check if DFS Strings Are Palindromes primarily test?

It tests array scanning plus hash lookup to track character counts efficiently along DFS paths.

Can this problem be solved by building strings at each node?

Technically yes, but it is inefficient. Bitmasking or frequency counts avoid O(n^2) time complexity.

What is the recommended space optimization for this problem?

Maintain a single bitmask or frequency array during DFS instead of storing full strings for each node.

How does GhostInterview handle DFS traversal efficiently?

It tracks cumulative character states along the path, instantly checking palindrome possibility at each node.

Are there variations of this problem I should practice?

Yes, BFS string palindromes, palindrome paths with dynamic updates, and weighted tree variants are useful extensions.

terminal

Solution

Solution 1: DFS + String Hashing

We can use Depth-First Search (DFS) to traverse the tree and compute the entire $\textit{dfsStr}$, while also determining the interval $[l, r]$ for each node.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

class Hashing:
    __slots__ = ["mod", "h", "p"]

    def __init__(self, s: List[str], base: int, mod: int):
        self.mod = mod
        self.h = [0] * (len(s) + 1)
        self.p = [1] * (len(s) + 1)
        for i in range(1, len(s) + 1):
            self.h[i] = (self.h[i - 1] * base + ord(s[i - 1])) % mod
            self.p[i] = (self.p[i - 1] * base) % mod

    def query(self, l: int, r: int) -> int:
        return (self.h[r] - self.h[l - 1] * self.p[r - l + 1]) % self.mod


class Solution:
    def findAnswer(self, parent: List[int], s: str) -> List[bool]:
        def dfs(i: int):
            l = len(dfsStr) + 1
            for j in g[i]:
                dfs(j)
            dfsStr.append(s[i])
            r = len(dfsStr)
            pos[i] = (l, r)

        n = len(s)
        g = [[] for _ in range(n)]
        for i in range(1, n):
            g[parent[i]].append(i)
        dfsStr = []
        pos = {}
        dfs(0)

        base, mod = 13331, 998244353
        h1 = Hashing(dfsStr, base, mod)
        h2 = Hashing(dfsStr[::-1], base, mod)
        ans = []
        for i in range(n):
            l, r = pos[i]
            k = r - l + 1
            v1 = h1.query(l, l + k // 2 - 1)
            v2 = h2.query(n - r + 1, n - r + 1 + k // 2 - 1)
            ans.append(v1 == v2)
        return ans

Continue Practicing

#3331 find subtree sizes after changes #3425 longest special path #3486 longest special path ii