3327. Check if DFS Strings Are Palindromes

HardTreeDepth-First SearchArrayHash TableStringHash Function

Problem Description

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.

Intuition

To solve this problem, we can employ a combination of Depth-First Search (DFS) and string hashing. The process begins by constructing the entire dfsStr for the tree starting from the root node. During the DFS traversal, we also track the interval [l, r] representing the positions within dfsStr for each node's subtree.

The primary task is to determine if the string formed by this subtree is a palindrome. Using direct character comparisons for palindromes can be inefficient for large inputs, hence using string hashing provides an efficient approach. By creating hash values for each node's subtree in dfsStr and its reverse, we can quickly compare these values to check for palindromes.

This approach effectively checks for palindrome properties within subtrees by leveraging properties of hash functions to reduce computational complexity. The hash values for the normal and reversed segments of dfsStr are compared to establish whether they are identical, indicating a palindrome structure.

Learn more about Tree and Depth-First Search patterns.

Solution Approach

To tackle the problem efficiently, the solution utilizes a combination of Depth-First Search (DFS) and string hashing, which optimizes the palindrome-checking process.

Step-by-Step Approach:

Tree Construction:
- Represent the tree using an adjacency list g, where each node points to its children.
DFS Traversal:
- Implement a recursive dfs function starting from node 0 (root) to construct the dfsStr string.
- While traversing, record the starting and ending positions [l, r] of each node's contributions in dfsStr. These positions are stored in the dictionary pos.
String Hashing:
- Use a Hashing class to precompute hash values for dfsStr and its reverse. This class works by maintaining hash values for substrings, which makes palindrome checks efficient.
- We choose a base, typically a large prime such as 13331, and another large prime 998244353 as the modulus.
Palindrome Check:
- For each node, retrieve its corresponding interval [l, r] from pos.
- Calculate the hash value for the segment from l to l + k//2 of dfsStr and its reverse counterpart using the hash functions.
- If both hash values match, it indicates the segment is a palindrome.
Build the Answer:
- For each node, append true to the answer list if the segment is a palindrome, otherwise false.

This hashing-based technique reduces the time complexity significantly when compared to character-by-character palindrome checks, making it possible to handle larger input sizes efficiently.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach step-by-step.

Example:

Suppose we have a tree with n = 5 nodes and the following parent array and string s:

parent = [-1, 0, 0, 1, 1]
s = "abcba"

This tree structure can be visualized as:

Node 0 is the root and has two children: 1 and 2.
Node 1 has two children: 3 and 4.

Step 1: Tree Construction

We first represent the tree using an adjacency list g. Here is how the tree connections are depicted:

g[0] = [1, 2]
g[1] = [3, 4]
g[2] = []
g[3] = []
g[4] = []

Step 2: DFS Traversal

Define the recursive function dfs(x) to build the dfsStr:

Start at the root (x = 0).
For each child y of x in increasing order, recursively call dfs(y).
Append the character s[x] to dfsStr.

Let's process the tree:

Starting at 0: Traverse through children 1 and 2.
Starting at 1: Traverse through children 3 and 4.
Visit 3: dfsStr = "b".
Visit 4: dfsStr = "ba".
Node 1: dfsStr = "bac".
Visit 2: dfsStr = "bacb".
Node 0: dfsStr = "bacba".

Step 3: String Hashing

Implement a Hashing class to calculate and store hash values efficiently for dfsStr = "bacba" and its reverse. Precompute hashes using a base and modulus to support constant-time comparisons.

Step 4: Palindrome Check

For each node:

Node 0: Check the entire dfsStr "bacba" with its reverse. This matches, indicating a palindrome.
Node 1: Check subtree segment dfsStr[0:3] = "bac"; not a palindrome.
Node 2: Check subtree segment dfsStr[3:4] = "b"; it's a palindrome.
Node 3: Check subtree segment dfsStr[0:1] = "b"; it's a palindrome.
Node 4: Check subtree segment dfsStr[1:2] = "a"; it's a palindrome.

Step 5: Build the Answer

The resultant boolean array answer is [true, false, true, true, true].

Thus, for each node, the segment checked is palindromic, except for node 1, which is not. This approach leverages efficient hashing to ensure swift palindrome verification.

Solution Implementation

1from typing import List
2
3class Hashing:
4    __slots__ = ["mod", "h", "p"]
5
6    def __init__(self, s: List[str], base: int, mod: int):
7        # Initialize modulo, prefix hash array, and power array
8        self.mod = mod
9        self.h = [0] * (len(s) + 1)
10        self.p = [1] * (len(s) + 1)
11      
12        # Precompute prefix hashes and powers of the base
13        for i in range(1, len(s) + 1):
14            self.h[i] = (self.h[i - 1] * base + ord(s[i - 1])) % mod
15            self.p[i] = (self.p[i - 1] * base) % mod
16
17    def query(self, l: int, r: int) -> int:
18        # Calculate hash of the substring s[l..r], using precomputed values
19        return (self.h[r] - self.h[l - 1] * self.p[r - l + 1]) % self.mod
20
21
22class Solution:
23    def findAnswer(self, parent: List[int], s: str) -> List[bool]:
24        # Helper function to perform DFS and record positions
25        def dfs(i: int):
26            l = len(dfs_str) + 1  # Start position for this node's string segment
27            for j in graph[i]:
28                dfs(j)  # Recursively process children
29            dfs_str.append(s[i])  # Append character corresponding to current node
30            r = len(dfs_str)      # End position for this node's string segment
31            positions[i] = (l, r) # Store the start and end position
32
33        n = len(s)  # Number of nodes
34        graph = [[] for _ in range(n)]  # Adjacency list of the tree
35      
36        # Construct tree from parent list
37        for i in range(1, n):
38            graph[parent[i]].append(i)
39      
40        dfs_str = []  # List to record the DFS traversal string
41        positions = {}  # Map node to its corresponding string segment positions
42        dfs(0)  # Start DFS from the root node (0)
43
44        base, mod = 13331, 998244353  # Base and modulus for hashing
45        h1 = Hashing(dfs_str, base, mod)  # Hashing for normal order
46        h2 = Hashing(dfs_str[::-1], base, mod)  # Hashing for reversed order
47      
48        ans = []  # List to store the boolean results
49        for i in range(n):
50            l, r = positions[i]  # Get positions in DFS string
51            k = r - l + 1  # Length of the segment
52            # Calculate hash values for comparing segments from the start and from the end
53            v1 = h1.query(l, l + k // 2 - 1)
54            v2 = h2.query(n - r + 1, n - r + 1 + k // 2 - 1)
55            ans.append(v1 == v2)  # Check if the first half is equal to the reverse of the first half
56      
57        return ans  # Return the list of palindrome checks for each subtree
58

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5// The Hashing class computes hash values for substrings using polynomial rolling hash
6class Hashing {
7    private final long[] p; // Array to store powers of base modulo mod
8    private final long[] h; // Array to store hash values up to each index
9    private final long mod; // The modulus value for hash computation
10
11    // Constructor initializes arrays and computes hash and power values
12    public Hashing(String word, long base, int mod) {
13        int n = word.length();
14        p = new long[n + 1];
15        h = new long[n + 1];
16        p[0] = 1; // Set the first power as 1 (base^0)
17        this.mod = mod; // Store mod value
18        for (int i = 1; i <= n; i++) {
19            p[i] = p[i - 1] * base % mod; // Compute powers of base
20            h[i] = (h[i - 1] * base + word.charAt(i - 1)) % mod; // Compute hash values
21        }
22    }
23
24    // Method to get hash value of a substring from index l to r (1-based index)
25    public long query(int l, int r) {
26        return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
27    }
28}
29
30// The Solution class provides a method to check palindromic subtree strings in a tree-like character array
31class Solution {
32    private char[] s; // Character array to store the string representation of nodes
33    private int[][] pos; // Array to store start and end positions of characters in the DFS traversal
34    private List<Integer>[] g; // Adjacency list to store the tree structure
35    private StringBuilder dfsStr = new StringBuilder(); // Builder to construct sequence of characters in DFS order
36
37    // Method to determine if the substring from each node in the tree forms a palindrome
38    public boolean[] findAnswer(int[] parent, String s) {
39        this.s = s.toCharArray(); // Convert string to char array for processing
40        int n = s.length();
41        g = new List[n]; // Initialize adjacency list
42        pos = new int[n][0]; // Initialize position array for each node
43        Arrays.setAll(g, k -> new ArrayList<>()); // Fill adjacency list with empty lists
44        for (int i = 1; i < n; ++i) {
45            g[parent[i]].add(i); // Populate adjacency list
46        }
47        dfs(0); // Perform DFS starting from root node
48        final int base = 13331; // Base for hashing
49        final int mod = 998244353; // Modulus for hashing
50        Hashing h1 = new Hashing(dfsStr.toString(), base, mod); // Hash object for direct order
51        Hashing h2 = new Hashing(new StringBuilder(dfsStr).reverse().toString(), base, mod); // Hash object for reverse order
52        boolean[] ans = new boolean[n]; // Array to store results for each node
53        for (int i = 0; i < n; ++i) {
54            int l = pos[i][0], r = pos[i][1]; // Get positions of current node
55            int k = r - l + 1; // Compute length of substring
56            long v1 = h1.query(l, l + k / 2 - 1); // Get hash of first half in direct order
57            long v2 = h2.query(n + 1 - r, n + 1 - r + k / 2 - 1); // Get hash of first half in reverse order
58            ans[i] = v1 == v2; // Check if the two halves are equal (palindrome check)
59        }
60        return ans; // Return results
61    }
62
63    // Recursively perform depth-first search to compute positions of characters in the DFS order
64    private void dfs(int i) {
65        int l = dfsStr.length() + 1; // Store starting position for current node
66        for (int j : g[i]) {
67            dfs(j); // Recur for each child
68        }
69        dfsStr.append(s[i]); // Add current node's character to the DFS string
70        int r = dfsStr.length(); // Store ending position for current node
71        pos[i] = new int[] {l, r}; // Record positions in the pos array
72    }
73}
74

1#include <vector>
2#include <string>
3#include <algorithm>
4
5using namespace std;
6
7class Hashing {
8private:
9    vector<long long> p; // Powers of base modulo mod
10    vector<long long> h; // Hash values for prefix substrings
11    long long mod; // Modulo value for hashing
12
13public:
14    // Constructor to initialize the `Hashing` object.
15    Hashing(string word, long long base, int mod) {
16        int n = word.size();
17        p.resize(n + 1); // Initialize vector for powers of base
18        h.resize(n + 1); // Initialize vector for hash values
19        p[0] = 1; // Base case: any number to the power of zero is 1
20        this->mod = mod; // Set the modulo value
21
22        // Calculate powers of the base modulo `mod` and prefix hashes
23        for (int i = 1; i <= n; i++) {
24            p[i] = (p[i - 1] * base) % mod; // Compute base^i % mod
25            // Compute the hash value for [0, i)
26            h[i] = (h[i - 1] * base + (word[i - 1] - 'a')) % mod;
27        }
28    }
29
30    // Function to get the hash value of substring `s[l, r]`
31    long long query(int l, int r) {
32        // Use properties of modular arithmetic to extract hash value of substring
33        return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
34    }
35};
36
37class Solution {
38public:
39    // Function to determine if the path to each node forms a palindrome
40    vector<bool> findAnswer(vector<int>& parent, string s) {
41        int n = s.size();
42        vector<int> g[n]; // Adjacency list for tree
43
44        // Build tree from parent array
45        for (int i = 1; i < n; ++i) {
46            g[parent[i]].push_back(i);
47        }
48
49        string dfsStr; // String to store DFS order
50        vector<pair<int, int>> pos(n); // Keep track of position indices for each node
51
52        // Depth First Search using lambda function
53        auto dfs = [&](auto&& dfs, int i) -> void {
54            int l = dfsStr.size() + 1; // Left index for current node's DFS string
55            for (int j : g[i]) {
56                dfs(dfs, j); // Recursively apply DFS
57            }
58            dfsStr.push_back(s[i]); // Add current character to DFS string
59            int r = dfsStr.size(); // Right index after adding character
60            pos[i] = {l, r}; // Store the position range for current node
61        };
62
63        // Perform DFS starting from root node (0)
64        dfs(dfs, 0);
65
66        const int base = 13331;
67        const int mod = 998244353;
68      
69        // Initialize hashing objects for original and reversed DFS strings
70        Hashing h1(dfsStr, base, mod);
71        reverse(dfsStr.begin(), dfsStr.end());
72        Hashing h2(dfsStr, base, mod);
73      
74        vector<bool> ans(n); // Result vector indicating if path forms palindrome
75
76        // Verify path to each node for palindrome property based on hash comparison
77        for (int i = 0; i < n; ++i) {
78            auto [l, r] = pos[i];
79            int k = r - l + 1; // Length of the substring
80
81            // Get hash values for corresponding halves of the original and reversed strings
82            long long v1 = h1.query(l, l + k / 2 - 1);
83            long long v2 = h2.query(n - r + 1, n - r + 1 + k / 2 - 1);
84
85            // Check if the hash values are the same
86            ans[i] = v1 == v2;
87        }
88
89        return ans;
90    }
91};
92

1// Define vectors for power of base and prefix hash
2let p: number[] = []; 
3let h: number[] = []; 
4let mod: number; 
5
6// Function to initialize powers and hashes
7function initializeHashing(word: string, base: number, modulus: number) {
8    const n = word.length;
9    p = new Array(n + 1).fill(0); // Initialize power array
10    h = new Array(n + 1).fill(0); // Initialize hash array
11    p[0] = 1; // Base case: Any number to the power of zero is 1
12    mod = modulus; // Set the global modulo
13
14    // Compute powers of base modulo mod and prefix hashes
15    for (let i = 1; i <= n; i++) {
16        p[i] = (p[i - 1] * base) % mod; // Compute base^i % mod
17        h[i] = (h[i - 1] * base + (word.charCodeAt(i - 1) - 'a'.charCodeAt(0))) % mod;
18    }
19}
20
21// Function to get the hashed value of a substring `s[l, r]`
22function queryHash(l: number, r: number): number {
23    return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
24}
25
26// Function to determine if the path to each node forms a palindrome
27function findAnswer(parent: number[], s: string): boolean[] {
28    const n = s.length;
29    const g: number[][] = Array.from({ length: n }, () => []); // Tree adjacency list
30
31    // Build tree from the parent array
32    for (let i = 1; i < n; i++) {
33        g[parent[i]].push(i);
34    }
35
36    let dfsStr = ''; // String representation of DFS traversal
37    const pos: Array<{l: number, r: number}> = Array(n); // Track position indices of nodes
38
39    // Recursive DFS function to capture traversal order
40    function dfs(i: number) {
41        const l = dfsStr.length + 1; // Left bound of current DFS position
42        for (const j of g[i]) {
43            dfs(j); // Recursive DFS on children
44        }
45        dfsStr += s[i]; // Add character to DFS string
46        const r = dfsStr.length; // Right bound after adding character
47        pos[i] = { l, r }; // Record position bounds for current node
48    }
49
50    // Start DFS from the root node (0)
51    dfs(0);
52
53    const base = 13331;
54    const mod = 998244353;
55
56    // Initialize hash for original and reversed DFS strings
57    initializeHashing(dfsStr, base, mod);
58    const h1 = [...h]; // Copy hash after original initialization
59
60    dfsStr = dfsStr.split('').reverse().join(''); // Reverse the DFS string
61    initializeHashing(dfsStr, base, mod);
62    const h2 = [...h]; // Copy hash after reverse initialization
63
64    const ans: boolean[] = new Array(n);
65
66    // Verify if the path to each node forms a palindrome
67    for (let i = 0; i < n; i++) {
68        const { l, r } = pos[i];
69        const k = r - l + 1; // Length of the substring
70      
71        // Calculate hash values for corresponding halves
72        const v1 = queryHash(l, l + Math.floor(k / 2) - 1);
73        const v2 = ((n - r + 1) in dfsStr) ? queryHash(n - r + 1, n - r + 1 + Math.floor(k / 2) - 1) : 0;
74      
75        // Check if hash values match
76        ans[i] = v1 === v2;
77    }
78
79    return ans;
80}
81

Time and Space Complexity

The time complexity of the findAnswer function is O(n), where n is the length of the string s. The reason for this complexity includes:

The depth-first search (DFS) operation traverses all nodes in the tree exactly once. Since the number of nodes is n, this operation takes O(n) time.
Constructing the Hashing objects involves iterating over the list dfsStr, which has a length of n. This process also takes O(n) time.
The loop that computes the result list ans also iterates n times, with each hashing query operation inside the loop being performed in constant time, resulting in an O(n) time complexity for this part.

Overall, each major step of the function involves operations linear in relation to n, leading to an overall time complexity of O(n).

The space complexity of the code is O(n), as it requires additional data structures of linear size, such as:

The dfsStr list, which stores the string characters in the order they are visited in the DFS, has n elements.
The pos dictionary maps up to n node indices to their respective positions, though the entries are created during the DFS traversal.
The Hashing objects each utilize space proportional to the length of dfsStr, which is n.

Consequently, the space complexity is dominated by these data structures, resulting in O(n).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: