3327. Check if DFS Strings Are Palindromes

HardTreeDepth-First SearchArrayHash TableStringHash Function
Leetcode Link

Problem Description

You have a tree with n nodes numbered from 0 to n - 1, where node 0 is the root. The tree structure is given by an array parent where parent[i] indicates the parent of node i. Since node 0 is the root, parent[0] = -1.

Each node i has a character s[i] associated with it.

The problem defines a special DFS traversal that builds a string dfsStr:

  • Starting from any node x, the DFS function:
    1. First recursively visits all children of x in increasing order of their node numbers
    2. After visiting all children, appends the character s[x] to dfsStr

Your task is to determine, for each node i from 0 to n - 1, whether starting a DFS from that node produces a palindrome string.

The output should be a boolean array answer where answer[i] is true if starting DFS from node i produces a palindrome in dfsStr, and false otherwise.

Example of DFS traversal: If we have a tree where node 0 has children 1 and 2, and node 1 has child 3:

  • DFS from node 0 would visit: node 1 → node 3 → append s[3] → append s[1] → node 2 → append s[2] → append s[0]
  • The resulting dfsStr would be: s[3] + s[1] + s[2] + s[0]

The solution uses string hashing to efficiently check palindromes. It first computes the complete DFS string starting from root (node 0) and records the position interval [l, r] for each subtree. Then it uses polynomial rolling hash to compare the forward and reverse hash values of each subtree's string segment to determine if it forms a palindrome.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • Yes: The problem explicitly involves a tree structure with nodes (0 to n-1) and edges defined by the parent-child relationships in the parent array.

Is it a tree?

  • Yes: The problem states we have a tree rooted at node 0. The parent array defines a tree structure where each node (except the root) has exactly one parent, and parent[0] = -1 indicates node 0 is the root.

DFS

  • Yes: This leads us directly to DFS as the appropriate algorithm.

Conclusion: The flowchart confirms that DFS (Depth-First Search) is the correct approach for this problem.

Why DFS is the Perfect Fit

The problem explicitly requires a DFS traversal pattern:

  1. Tree Traversal Requirement: We need to traverse each subtree starting from different nodes to build the dfsStr string.

  2. Specific Traversal Order: The problem mandates visiting children in increasing order of their node numbers, then appending the current node's character - this is a post-order DFS traversal.

  3. Subtree Processing: For each node i, we need to process its entire subtree to generate the corresponding substring. DFS naturally handles subtree exploration.

  4. Recursive Nature: The problem description itself defines a recursive DFS function that:

    • Recursively visits all children first
    • Then processes the current node (appends its character)

The solution implements DFS to:

  • Build the complete dfsStr starting from the root
  • Track the position intervals [l, r] for each subtree's contribution to the string
  • Use these intervals with string hashing to efficiently check palindromes
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that we don't need to run DFS from every single node separately - that would be inefficient. Instead, we can observe that when we run DFS from any node, we're essentially getting a substring of what we'd get from a complete DFS starting from a higher ancestor.

Think about it this way: when we perform DFS from the root (node 0), we visit every node in the tree and build the complete dfsStr. Now, if we were to start DFS from any other node i, we'd only visit node i and its subtree - this produces a substring that already exists within the complete dfsStr.

This leads to our first breakthrough: we only need to run DFS once from the root, and during this traversal, we can track where each subtree's contribution starts and ends in the final string. For each node i, we record its interval [l, r] representing the positions in dfsStr that would be generated if we started DFS from node i.

The second challenge is checking if each substring is a palindrome. A naive approach would check character by character for each substring, but this is slow. Here's where string hashing comes in - it's a technique that converts strings into numerical values (hashes) for fast comparison.

For palindrome checking, we need a clever trick: a string is a palindrome if its first half matches its second half when reversed. So we:

  1. Compute hash values for the forward string (dfsStr)
  2. Compute hash values for the reversed string (dfsStr[::-1])
  3. For each substring defined by interval [l, r], compare the hash of its first half with the hash of the corresponding position in the reversed string

The beauty of this approach is that we transform an O(n²) problem (running DFS from each node and checking palindromes) into an O(n) solution (one DFS traversal plus O(1) palindrome checks using precomputed hashes).

The polynomial rolling hash with base 13331 and modulo 998244353 ensures very low collision probability while keeping computations efficient.

Learn more about Tree and Depth-First Search patterns.

Solution Implementation

1from typing import List 2 3 4class Hashing: 5 """Rolling hash implementation for string hashing.""" 6 __slots__ = ["mod", "hash_values", "powers"] 7 8 def __init__(self, string: List[str], base: int, mod: int): 9 """ 10 Initialize the hashing object with precomputed hash values and powers. 11 12 Args: 13 string: List of characters to hash 14 base: Base for polynomial rolling hash 15 mod: Modulo value to prevent overflow 16 """ 17 self.mod = mod 18 self.hash_values = [0] * (len(string) + 1) 19 self.powers = [1] * (len(string) + 1) 20 21 # Precompute hash values and powers of base 22 for i in range(1, len(string) + 1): 23 self.hash_values[i] = (self.hash_values[i - 1] * base + ord(string[i - 1])) % mod 24 self.powers[i] = (self.powers[i - 1] * base) % mod 25 26 def query(self, left: int, right: int) -> int: 27 """ 28 Get the hash value of substring from position left to right (1-indexed). 29 30 Args: 31 left: Starting position (1-indexed) 32 right: Ending position (1-indexed) 33 34 Returns: 35 Hash value of the substring 36 """ 37 return (self.hash_values[right] - self.hash_values[left - 1] * self.powers[right - left + 1]) % self.mod 38 39 40class Solution: 41 def findAnswer(self, parent: List[int], s: str) -> List[bool]: 42 """ 43 Check if each node's subtree forms a palindrome when traversed in DFS order. 44 45 Args: 46 parent: Parent array where parent[i] is the parent of node i 47 s: String where s[i] is the character at node i 48 49 Returns: 50 List of booleans indicating if each node's subtree is a palindrome 51 """ 52 def dfs(node: int) -> None: 53 """ 54 Perform DFS traversal and build the DFS string while recording node positions. 55 56 Args: 57 node: Current node being visited 58 """ 59 # Record the starting position for this node's subtree 60 left_pos = len(dfs_string) + 1 61 62 # Recursively visit all children 63 for child in adjacency_list[node]: 64 dfs(child) 65 66 # Add current node's character to DFS string 67 dfs_string.append(s[node]) 68 69 # Record the ending position for this node's subtree 70 right_pos = len(dfs_string) 71 node_positions[node] = (left_pos, right_pos) 72 73 # Build adjacency list representation of the tree 74 n = len(s) 75 adjacency_list = [[] for _ in range(n)] 76 for i in range(1, n): 77 adjacency_list[parent[i]].append(i) 78 79 # Perform DFS to build the string and record positions 80 dfs_string = [] 81 node_positions = {} 82 dfs(0) 83 84 # Initialize hashing parameters 85 BASE = 13331 86 MOD = 998244353 87 88 # Create hash objects for forward and reverse strings 89 forward_hash = Hashing(dfs_string, BASE, MOD) 90 reverse_hash = Hashing(dfs_string[::-1], BASE, MOD) 91 92 # Check if each node's subtree forms a palindrome 93 result = [] 94 for i in range(n): 95 left, right = node_positions[i] 96 subtree_length = right - left + 1 97 98 # Compare first half with reversed second half 99 first_half_hash = forward_hash.query(left, left + subtree_length // 2 - 1) 100 second_half_reversed_hash = reverse_hash.query(n - right + 1, n - right + 1 + subtree_length // 2 - 1) 101 102 # Check if the hashes match (indicating a palindrome) 103 result.append(first_half_hash == second_half_reversed_hash) 104 105 return result 106
1/** 2 * Rolling hash utility class for efficient substring hash computation 3 */ 4class Hashing { 5 private final long[] powers; // powers[i] = base^i mod mod 6 private final long[] prefixHash; // prefixHash[i] = hash of s[0..i-1] 7 private final long mod; 8 9 /** 10 * Initialize the hashing structure for a given string 11 * @param word The input string to be hashed 12 * @param base The base for polynomial rolling hash 13 * @param mod The modulo value to prevent overflow 14 */ 15 public Hashing(String word, long base, int mod) { 16 int n = word.length(); 17 powers = new long[n + 1]; 18 prefixHash = new long[n + 1]; 19 powers[0] = 1; 20 this.mod = mod; 21 22 // Precompute powers of base and prefix hashes 23 for (int i = 1; i <= n; i++) { 24 powers[i] = powers[i - 1] * base % mod; 25 prefixHash[i] = (prefixHash[i - 1] * base + word.charAt(i - 1)) % mod; 26 } 27 } 28 29 /** 30 * Query the hash value of substring from index l-1 to r-1 (1-indexed input) 31 * @param l Starting position (1-indexed) 32 * @param r Ending position (1-indexed) 33 * @return Hash value of the substring 34 */ 35 public long query(int l, int r) { 36 // Calculate hash of substring using prefix difference 37 // Add mod before final mod to handle negative values 38 return (prefixHash[r] - prefixHash[l - 1] * powers[r - l + 1] % mod + mod) % mod; 39 } 40} 41 42/** 43 * Solution class to determine if each node's subtree forms a palindrome 44 */ 45class Solution { 46 private char[] nodeCharacters; // Characters at each node 47 private int[][] nodePositions; // Start and end positions in DFS string for each node 48 private List<Integer>[] adjacencyList; // Tree adjacency list (children of each node) 49 private StringBuilder dfsTraversal = new StringBuilder(); // DFS traversal string 50 51 /** 52 * Find whether each node's subtree forms a palindrome string 53 * @param parent Array where parent[i] is the parent of node i 54 * @param s String where s[i] is the character at node i 55 * @return Boolean array where result[i] indicates if node i's subtree is palindrome 56 */ 57 public boolean[] findAnswer(int[] parent, String s) { 58 this.nodeCharacters = s.toCharArray(); 59 int n = s.length(); 60 61 // Initialize adjacency list for tree representation 62 adjacencyList = new List[n]; 63 nodePositions = new int[n][0]; 64 Arrays.setAll(adjacencyList, k -> new ArrayList<>()); 65 66 // Build tree structure from parent array 67 for (int i = 1; i < n; ++i) { 68 adjacencyList[parent[i]].add(i); 69 } 70 71 // Perform DFS to build the traversal string 72 dfs(0); 73 74 // Hash configuration 75 final int BASE = 13331; 76 final int MOD = 998244353; 77 78 // Create hash structures for forward and reverse strings 79 Hashing forwardHash = new Hashing(dfsTraversal.toString(), BASE, MOD); 80 Hashing reverseHash = new Hashing(new StringBuilder(dfsTraversal).reverse().toString(), BASE, MOD); 81 82 // Check palindrome for each node's subtree 83 boolean[] result = new boolean[n]; 84 for (int i = 0; i < n; ++i) { 85 int left = nodePositions[i][0]; 86 int right = nodePositions[i][1]; 87 int subtreeLength = right - left + 1; 88 89 // Compare first half with reversed second half 90 long firstHalfHash = forwardHash.query(left, left + subtreeLength / 2 - 1); 91 long secondHalfReversedHash = reverseHash.query(n + 1 - right, n + 1 - right + subtreeLength / 2 - 1); 92 93 result[i] = (firstHalfHash == secondHalfReversedHash); 94 } 95 96 return result; 97 } 98 99 /** 100 * Depth-first search to build the DFS traversal string 101 * Children are visited first, then the current node's character is appended 102 * @param nodeIndex Current node being visited 103 */ 104 private void dfs(int nodeIndex) { 105 // Record starting position (1-indexed) for this node's subtree 106 int startPosition = dfsTraversal.length() + 1; 107 108 // Recursively visit all children 109 for (int child : adjacencyList[nodeIndex]) { 110 dfs(child); 111 } 112 113 // Append current node's character 114 dfsTraversal.append(nodeCharacters[nodeIndex]); 115 116 // Record ending position for this node's subtree 117 int endPosition = dfsTraversal.length(); 118 nodePositions[nodeIndex] = new int[] {startPosition, endPosition}; 119 } 120} 121
1class Hashing { 2private: 3 vector<long long> power; // power[i] stores base^i mod modulo 4 vector<long long> hash; // hash[i] stores hash value of prefix [0, i-1] 5 long long modulo; // modulo for hash computation 6 7public: 8 /** 9 * Constructor to build polynomial rolling hash for a string 10 * @param word: input string to hash 11 * @param base: base for polynomial hash 12 * @param mod: modulo value for hash computation 13 */ 14 Hashing(string word, long long base, int mod) { 15 int n = word.size(); 16 power.resize(n + 1); 17 hash.resize(n + 1); 18 power[0] = 1; 19 this->modulo = mod; 20 21 // Precompute powers of base and prefix hashes 22 for (int i = 1; i <= n; i++) { 23 power[i] = (power[i - 1] * base) % mod; 24 hash[i] = (hash[i - 1] * base + word[i - 1] - 'a') % mod; 25 } 26 } 27 28 /** 29 * Query hash value for substring [l-1, r-1] (1-indexed input) 30 * @param l: left boundary (1-indexed) 31 * @param r: right boundary (1-indexed) 32 * @return: hash value of substring 33 */ 34 long long query(int l, int r) { 35 // Extract hash of substring using prefix hash difference 36 return (hash[r] - hash[l - 1] * power[r - l + 1] % modulo + modulo) % modulo; 37 } 38}; 39 40class Solution { 41public: 42 /** 43 * Find if each node's subtree forms a palindrome when traversed in DFS order 44 * @param parent: parent[i] is the parent of node i (parent[0] = -1 for root) 45 * @param s: string where s[i] is the character at node i 46 * @return: vector where ans[i] indicates if subtree rooted at i forms palindrome 47 */ 48 vector<bool> findAnswer(vector<int>& parent, string s) { 49 int n = s.size(); 50 51 // Build adjacency list representation of tree 52 vector<int> adjacencyList[n]; 53 for (int i = 1; i < n; ++i) { 54 adjacencyList[parent[i]].push_back(i); 55 } 56 57 string dfsString; // String formed by DFS traversal 58 vector<pair<int, int>> position(n); // position[i] = {left, right} boundaries of node i's subtree in dfsString 59 60 // DFS to build the traversal string (children first, then current node) 61 auto dfs = [&](this auto&& dfs, int node) -> void { 62 int left = dfsString.size() + 1; // 1-indexed position 63 64 // Recursively visit all children 65 for (int child : adjacencyList[node]) { 66 dfs(child); 67 } 68 69 // Append current node's character 70 dfsString.push_back(s[node]); 71 int right = dfsString.size(); // 1-indexed position 72 73 position[node] = {left, right}; 74 }; 75 76 // Start DFS from root (node 0) 77 dfs(0); 78 79 // Hash configuration 80 const int BASE = 13331; 81 const int MODULO = 998244353; 82 83 // Create hash for original DFS string 84 Hashing forwardHash(dfsString, BASE, MODULO); 85 86 // Create hash for reversed DFS string 87 reverse(dfsString.begin(), dfsString.end()); 88 Hashing reverseHash(dfsString, BASE, MODULO); 89 90 // Check palindrome for each node's subtree 91 vector<bool> answer(n); 92 for (int i = 0; i < n; ++i) { 93 auto [left, right] = position[i]; 94 int length = right - left + 1; 95 96 // Compare first half with reversed second half 97 long long firstHalfHash = forwardHash.query(left, left + length / 2 - 1); 98 long long secondHalfReversedHash = reverseHash.query(n - right + 1, n - right + 1 + length / 2 - 1); 99 100 answer[i] = (firstHalfHash == secondHalfReversedHash); 101 } 102 103 return answer; 104 } 105}; 106
1// Global variables and types 2let power: number[] = []; // power[i] stores base^i mod modulo 3let hash: number[] = []; // hash[i] stores hash value of prefix [0, i-1] 4let modulo: number = 0; // modulo for hash computation 5 6/** 7 * Build polynomial rolling hash for a string 8 * @param word - input string to hash 9 * @param base - base for polynomial hash 10 * @param mod - modulo value for hash computation 11 */ 12function initializeHashing(word: string, base: number, mod: number): void { 13 const n = word.length; 14 power = new Array(n + 1).fill(0); 15 hash = new Array(n + 1).fill(0); 16 power[0] = 1; 17 modulo = mod; 18 19 // Precompute powers of base and prefix hashes 20 for (let i = 1; i <= n; i++) { 21 power[i] = (power[i - 1] * base) % mod; 22 hash[i] = (hash[i - 1] * base + word.charCodeAt(i - 1) - 'a'.charCodeAt(0)) % mod; 23 } 24} 25 26/** 27 * Query hash value for substring [l-1, r-1] (1-indexed input) 28 * @param l - left boundary (1-indexed) 29 * @param r - right boundary (1-indexed) 30 * @returns hash value of substring 31 */ 32function queryHash(l: number, r: number): number { 33 // Extract hash of substring using prefix hash difference 34 return (hash[r] - hash[l - 1] * power[r - l + 1] % modulo + modulo) % modulo; 35} 36 37/** 38 * Find if each node's subtree forms a palindrome when traversed in DFS order 39 * @param parent - parent[i] is the parent of node i (parent[0] = -1 for root) 40 * @param s - string where s[i] is the character at node i 41 * @returns array where ans[i] indicates if subtree rooted at i forms palindrome 42 */ 43function findAnswer(parent: number[], s: string): boolean[] { 44 const n = s.length; 45 46 // Build adjacency list representation of tree 47 const adjacencyList: number[][] = Array.from({ length: n }, () => []); 48 for (let i = 1; i < n; i++) { 49 adjacencyList[parent[i]].push(i); 50 } 51 52 let dfsString = ""; // String formed by DFS traversal 53 const position: [number, number][] = new Array(n); // position[i] = [left, right] boundaries of node i's subtree in dfsString 54 55 // DFS to build the traversal string (children first, then current node) 56 const dfs = (node: number): void => { 57 const left = dfsString.length + 1; // 1-indexed position 58 59 // Recursively visit all children 60 for (const child of adjacencyList[node]) { 61 dfs(child); 62 } 63 64 // Append current node's character 65 dfsString += s[node]; 66 const right = dfsString.length; // 1-indexed position 67 68 position[node] = [left, right]; 69 }; 70 71 // Start DFS from root (node 0) 72 dfs(0); 73 74 // Hash configuration 75 const BASE = 13331; 76 const MODULO = 998244353; 77 78 // Create hash for original DFS string 79 initializeHashing(dfsString, BASE, MODULO); 80 const forwardPower = [...power]; 81 const forwardHash = [...hash]; 82 83 // Create hash for reversed DFS string 84 const reversedDfsString = dfsString.split('').reverse().join(''); 85 initializeHashing(reversedDfsString, BASE, MODULO); 86 const reversePower = [...power]; 87 const reverseHash = [...hash]; 88 89 // Check palindrome for each node's subtree 90 const answer: boolean[] = new Array(n); 91 for (let i = 0; i < n; i++) { 92 const [left, right] = position[i]; 93 const length = right - left + 1; 94 95 // Compare first half with reversed second half 96 // Restore forward hash arrays for query 97 power = forwardPower; 98 hash = forwardHash; 99 const firstHalfHash = queryHash(left, left + Math.floor(length / 2) - 1); 100 101 // Restore reverse hash arrays for query 102 power = reversePower; 103 hash = reverseHash; 104 const secondHalfReversedHash = queryHash(n - right + 1, n - right + 1 + Math.floor(length / 2) - 1); 105 106 answer[i] = (firstHalfHash === secondHalfReversedHash); 107 } 108 109 return answer; 110} 111

Solution Approach

The implementation consists of three main components: DFS traversal, string hashing, and palindrome verification.

Step 1: Build the Tree Structure

First, we construct an adjacency list representation of the tree from the parent array:

g = [[] for _ in range(n)] for i in range(1, n):  g[parent[i]].append(i)

This creates a list where g[i] contains all children of node i.

Step 2: DFS Traversal to Build dfsStr

We perform a single DFS from the root to build the complete dfsStr and record position intervals:

def dfs(i: int):  l = len(dfsStr) + 1 # Start position (1-indexed)  for j in g[i]: # Visit children in order  dfs(j)  dfsStr.append(s[i]) # Append current node's character  r = len(dfsStr) # End position  pos[i] = (l, r) # Store interval for node i

The DFS follows the problem's specification:

  • Visit all children recursively in increasing order (already sorted in adjacency list)
  • After visiting children, append the current node's character
  • Track the interval [l, r] where node i's subtree contributes to dfsStr

Step 3: String Hashing Setup

The Hashing class implements polynomial rolling hash:

self.h[i] = (self.h[i - 1] * base + ord(s[i - 1])) % mod self.p[i] = (self.p[i - 1] * base) % mod
  • h[i] stores the hash value of prefix s[0:i]
  • p[i] stores base^i % mod for efficient hash computation
  • The query(l, r) method returns the hash of substring s[l-1:r] using the formula: (h[r] - h[l-1] * p[r-l+1]) % mod

We create two hash objects:

  • h1 for the forward string dfsStr
  • h2 for the reversed string dfsStr[::-1]

Step 4: Palindrome Checking

For each node i, we check if its substring is a palindrome:

for i in range(n):  l, r = pos[i]  k = r - l + 1 # Length of substring  v1 = h1.query(l, l + k // 2 - 1) # First half hash  v2 = h2.query(n - r + 1, n - r + 1 + k // 2 - 1) # Corresponding reversed half  ans.append(v1 == v2)

The palindrome check works by:

  1. Getting the substring length k
  2. Computing hash of the first half from the forward string
  3. Computing hash of the corresponding position in the reversed string
  4. If both hashes match, the substring is a palindrome

The key insight is that for a palindrome, reading the first half forward should match reading the second half backward. By using the reversed string's hash, we can check this condition in O(1) time.

Time Complexity: O(n) - one DFS traversal plus O(n) hash computations Space Complexity: O(n) - for storing the tree, dfsStr, and hash arrays

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

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

Given:

  • n = 4 nodes (0, 1, 2, 3)
  • parent = [-1, 0, 0, 1] (tree structure: 0 is root, 1 and 2 are children of 0, 3 is child of 1)
  • s = "abba" (node 0 has 'a', node 1 has 'b', node 2 has 'b', node 3 has 'a')

Step 1: Build Tree Structure

Adjacency list: g[0] = [1, 2] (node 0's children) g[1] = [3] (node 1's children) g[2] = [] (node 2 has no children) g[3] = [] (node 3 has no children)

Step 2: DFS Traversal from Root Starting DFS from node 0:

  1. Visit node 1 (child of 0)
    • Visit node 3 (child of 1)
      • No children, append s[3]='a' → dfsStr = "a", pos[3] = (1,1)
    • Children done, append s[1]='b' → dfsStr = "ab", pos[1] = (1,2)
  2. Visit node 2 (child of 0)
    • No children, append s[2]='b' → dfsStr = "abb", pos[2] = (3,3)
  3. Children done, append s[0]='a' → dfsStr = "abba", pos[0] = (1,4)

Final dfsStr = "abba"

Position intervals:

  • pos[0] = (1,4) → substring "abba"
  • pos[1] = (1,2) → substring "ab"
  • pos[2] = (3,3) → substring "b"
  • pos[3] = (1,1) → substring "a"

Step 3: String Hashing

  • Forward hash h1 on "abba"
  • Reverse hash h2 on "abba" reversed = "abba"

Step 4: Palindrome Checking

For node 0: interval (1,4), length k=4

  • First half (positions 1-2): "ab"
  • Check against reversed positions: comparing "ab" with "ba" reversed
  • Hash values match → "abba" is palindrome → answer[0] = true

For node 1: interval (1,2), length k=2

  • First half (position 1): "a"
  • Check against reversed position: comparing "a" with "b"
  • Hash values don't match → "ab" is not palindrome → answer[1] = false

For node 2: interval (3,3), length k=1

  • Single character "b" is always palindrome → answer[2] = true

For node 3: interval (1,1), length k=1

  • Single character "a" is always palindrome → answer[3] = true

Final Answer: [true, false, true, true]

This example demonstrates how we build the complete DFS string once, track position intervals for each node's subtree, and use hashing to efficiently check palindromes without repeatedly running DFS from each node.

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of several main components:

  • Building the adjacency list g from the parent array takes O(n) time
  • The DFS traversal visits each node exactly once, appending each character to dfsStr, which takes O(n) time total
  • Initializing the two Hashing objects (h1 and h2) each takes O(n) time to compute the prefix hashes and powers
  • The final loop iterates through all n nodes, and for each node:
    • Retrieves the position bounds in O(1)
    • Performs two hash queries, each in O(1) time
    • Compares the hash values in O(1)

Therefore, the overall time complexity is O(n) + O(n) + O(n) + O(n) + O(n) = O(n).

Space Complexity: O(n)

The space usage includes:

  • The adjacency list g storing the tree structure: O(n)
  • The dfsStr list containing all characters from the DFS traversal: O(n)
  • The pos dictionary storing position pairs for each node: O(n)
  • Two Hashing objects, each maintaining arrays h and p of size n+1: O(n) each
  • The ans list storing boolean results: O(n)
  • The recursion stack for DFS in the worst case (skewed tree): O(n)

The total space complexity is O(n).

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

Common Pitfalls

1. Hash Collision Leading to False Positives

The Pitfall: The current implementation uses a single hash function with one base and modulo value. While polynomial rolling hash is efficient, it can produce collisions where different strings yield the same hash value, causing the algorithm to incorrectly identify non-palindromes as palindromes.

Example Scenario: Two different substrings might hash to the same value by chance, especially with a single modulo operation. This is particularly problematic in competitive programming or when dealing with adversarial inputs.

Solution: Use double hashing with two different prime moduli to significantly reduce collision probability:

class DoubleHashing:  def __init__(self, string: List[str], base: int):  self.mod1 = 10**9 + 7  self.mod2 = 998244353  n = len(string)   self.h1 = [0] * (n + 1)  self.h2 = [0] * (n + 1)  self.p1 = [1] * (n + 1)  self.p2 = [1] * (n + 1)   for i in range(1, n + 1):  self.h1[i] = (self.h1[i - 1] * base + ord(string[i - 1])) % self.mod1  self.h2[i] = (self.h2[i - 1] * base + ord(string[i - 1])) % self.mod2  self.p1[i] = (self.p1[i - 1] * base) % self.mod1  self.p2[i] = (self.p2[i - 1] * base) % self.mod2   def query(self, left: int, right: int) -> tuple:  hash1 = (self.h1[right] - self.h1[left - 1] * self.p1[right - left + 1]) % self.mod1  hash2 = (self.h2[right] - self.h2[left - 1] * self.p2[right - left + 1]) % self.mod2  return (hash1, hash2)

Then modify the palindrome check to compare both hash values:

v1 = forward_hash.query(left, left + subtree_length // 2 - 1) v2 = reverse_hash.query(n - right + 1, n - right + 1 + subtree_length // 2 - 1) result.append(v1[0] == v2[0] and v1[1] == v2[1])

2. Integer Overflow in Hash Computation

The Pitfall: Even with modulo operations, intermediate calculations like self.h[i - 1] * base can overflow before the modulo is applied, especially in languages with fixed integer sizes or when using very large base values.

Solution: Ensure all intermediate operations stay within bounds by applying modulo more frequently:

def __init__(self, string: List[str], base: int, mod: int):  self.mod = mod  self.hash_values = [0] * (len(string) + 1)  self.powers = [1] * (len(string) + 1)   for i in range(1, len(string) + 1):  # Apply modulo after each operation to prevent overflow  self.hash_values[i] = ((self.hash_values[i - 1] % mod) * (base % mod)) % mod  self.hash_values[i] = (self.hash_values[i] + ord(string[i - 1])) % mod  self.powers[i] = ((self.powers[i - 1] % mod) * (base % mod)) % mod

3. Off-by-One Errors in Index Calculation

The Pitfall: The mixing of 0-indexed arrays with 1-indexed position tracking can easily lead to off-by-one errors. The current code uses 1-indexed positions for the hash queries while Python uses 0-indexed arrays, creating confusion.

Solution: Add clear documentation and validation:

def query(self, left: int, right: int) -> int:  """  Get hash of substring [left, right] where positions are 1-indexed.  """  assert 1 <= left <= right <= len(self.hash_values) - 1, f"Invalid range: [{left}, {right}]"   # Calculate with clear variable names  substring_length = right - left + 1  hash_value = (self.hash_values[right] -  self.hash_values[left - 1] * self.powers[substring_length]) % self.mod   # Handle negative modulo results  return (hash_value + self.mod) % self.mod

4. Incorrect Handling of Odd-Length Palindromes

The Pitfall: The current implementation only compares the first half with the reversed second half using integer division (k // 2). For odd-length strings, this ignores the middle character, which could lead to incorrect results.

Solution: Handle odd and even length cases explicitly:

for i in range(n):  left, right = node_positions[i]  subtree_length = right - left + 1   if subtree_length == 1:  # Single character is always a palindrome  result.append(True)  else:  # For even length: compare two halves  # For odd length: compare two halves excluding middle  half_length = subtree_length // 2   first_half = forward_hash.query(left, left + half_length - 1)   # Adjust for odd length by potentially skipping middle character  if subtree_length % 2 == 0:  second_half_start = n - right + 1  else:  second_half_start = n - right + 2 # Skip middle character in reverse   second_half = reverse_hash.query(second_half_start,  second_half_start + half_length - 1)   result.append(first_half == second_half)
Loading...
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https assets algo monster cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS As the name suggests

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More