137. Count String Prefixes on Tree Paths

Occurrences of Every Prefix in Undirected Tree

You are given an undirected tree where each node contains exactly one lowercase English letter. You are also given a string s.

For every prefix of s, find how many times that prefix appears in the tree.

A prefix appears in the tree if you can choose an ordered simple path of nodes such that the sequence of letters on that path is exactly equal to that prefix.

Since the tree is undirected, a valid path may move in any direction across edges. In a rooted view, the path may go down, up, or up and then down.

Return the answer as a list where the value at index i is the number of occurrences of the prefix s[0..i].

Method Signature

List<Integer> countPrefixOccurrences(int n, List<String> edges, String letters, String s)

n is the number of nodes, labeled from 0 to n - 1.
edges contains exactly n - 1 strings, where each string is in the format "u v" and represents an undirected edge between nodes u and v.
letters.charAt(i) is the letter stored at node i.
s is the given string whose prefixes must be counted.
The returned list has length s.length().
The value at index i is the number of ordered simple paths whose letter sequence equals s.substring(0, i + 1).

Occurrence Rules

A path is a sequence of distinct nodes where every adjacent pair is connected by an edge.
Each occurrence is counted by traversal order, not just by the set of nodes.
If the same undirected path matches in both directions, both ordered traversals are counted separately.
A path may start at any node in the tree.
A path does not need to stay inside one subtree of any chosen root.

Constraints

1 ≤ n ≤ 20,000
edges.size() = n - 1
letters.length() = n
1 ≤ s.length() ≤ 20,000
letters and s contain only lowercase English letters
The given graph is guaranteed to be a valid tree

Return Format

Return a List<Integer> named answer such that:

answer.get(i) = number of occurrences of the prefix s[0..i] in the tree.

Examples

Example 1

countPrefixOccurrences(n = 5, edges = List.of("0 1", "1 2", "1 3", "3 4"), letters = "ababa", s = "aba") → List.of(3, 3, 2)

Prefix "a" appears 3 times because there are 3 nodes with letter 'a'. Prefix "ab" appears 3 times on ordered paths 0 -> 1, 2 -> 1, and 4 -> 3. Prefix "aba" appears 2 times on ordered paths 0 -> 1 -> 2 and 2 -> 1 -> 0.

Example 2

countPrefixOccurrences(n = 4, edges = List.of("0 1", "0 2", "0 3"), letters = "baca", s = "abc") → List.of(2, 2, 2)

The node letters are: node 0 = 'b', node 1 = 'a', node 2 = 'c', node 3 = 'a'. Prefix "a" appears at nodes 1 and 3. Prefix "ab" appears on paths 1 -> 0 and 3 -> 0. Prefix "abc" appears on paths 1 -> 0 -> 2 and 3 -> 0 -> 2. This example shows that a valid match can move up and then down in the undirected tree.

Example 3

countPrefixOccurrences(n = 3, edges = List.of("0 1", "1 2"), letters = "aab", s = "aaa") → List.of(2, 2, 0)

Prefix "a" appears at nodes 0 and 1. Prefix "aa" appears on ordered paths 0 -> 1 and 1 -> 0. Prefix "aaa" appears 0 times because occurrences must use simple paths, so revisiting a node is not allowed.