Salesforce Online Assessment Tree and String DP Solutions

1. Collect Opportunity Data in a Tree

You are given an undirected tree with n nodes labeled from 0 to n - 1. The tree is defined by n - 1 edges.

Each node represents a branch office. You are also given a binary array opportunityData of size n, where:

• opportunityData[i] = 1 means branch i contains important data.
• opportunityData[i] = 0 means it does not.

You may start at any node.

You can traverse edges in both directions.

You must start and end at the same node.

Special Rule

When you are at a node, you can collect data from all nodes within distance ≤ 2 edges from your current location.

Goal

Return the minimum number of edges you must traverse in order to collect all important data.

Example 1

**Input**: n = 11 edges = [[0,1],[0,2],[0,6],[1,3],[1,4],[3,10],[6,7],[7,8],[8,9]] opportunityData = [0,0,1,1,0,0,0,0,0,1,1]

**Output**: 6 

Explanation:

Nodes 2, 3, 9, 10 contain data.

One optimal strategy:

• Start at node 1
• From node 1, collect data at 3 and 10 (within distance 2)
• Travel to node 0 and collect 2
• Travel toward node 7 to collect 9
• Return to the starting node

Total edges traversed = 6

Constraints

• 2 ≤ n ≤ 10^5
• edges.length == n - 1
• The input graph is a valid tree
• opportunityData[i] ∈ {0, 1}

2. Replace '?' to Avoid Adjacent Duplicates

You are given a string s consisting of lowercase English letters ('a'–'z') and the character '?'.

Each '?' can be replaced with any lowercase English letter.

Return the total number of ways to replace all '?' such that the final string has no two adjacent identical characters.

Since the answer may be large, **return** it modulo 10^9 + 7.

Example 1

**Input**: s = "??"

**Output**: 650 

Explanation:

• First character: 26 choices
• Second character: 25 choices (cannot equal previous)
• Total = 26 × 25 = 650

Constraints

• 1 ≤ s.length ≤ 10^5
• s[i] is lowercase English letter or '?'

3. Strings With No k Consecutive Identical Characters

You are given two integers:

• n: length of string
• k: maximum allowed consecutive identical characters

A string is invalid if it contains k or more consecutive identical characters.

Return the total number of strings of length n formed using lowercase English letters such that no character appears k or more times consecutively.

Return the answer modulo 10^9 + 7.

Example 1

**Input**: n = 3, k = 2 Output: 16250 

Constraints

• 1 ≤ n ≤ 10^5
• 1 ≤ k < n