Longest Path With Different Adjacent Characters

Longest Path With Different Adjacent Characters - Problem

Array String Tree Depth-First Search Graph Topological Sort Hard

You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed 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.

Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them.

Input & Output

Example 1 — Basic Tree

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

› Output: 3

💡 Note: The longest valid path is 3→1→0→2 or 4→1→0→2 with length 3, where no adjacent nodes have the same character.

Example 2 — All Same Characters

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

› Output: 1

💡 Note: Since all nodes have the same character 'a', no path with different adjacent characters can have length > 1.

Example 3 — Linear Tree

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

› Output: 4

💡 Note: The path 0→1→2→3 has alternating characters a,b,a,b so the entire tree forms one valid path of length 4.

Constraints

n == parent.length == s.length
1 ≤ n ≤ 10⁵
parent[0] == -1
0 ≤ parent[i] ≤ n - 1 for i ≥ 1
parent represents a valid tree
s consists of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree with parent array [-1,0,0,1,1,2] and characters 'abacbe'

Find Valid Paths

Identify paths where adjacent nodes have different characters

Maximum Length

Return length of longest valid path found

Key Takeaway

🎯 Key Insight: Use DFS to combine the longest valid paths from each node's children, similar to finding tree diameter

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is to treat this as a tree diameter problem where we find the longest path by combining the two longest valid paths from each node's children. The optimal DFS approach visits each node once and combines child paths while respecting character constraints. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - All Pairs DFS	O(n³)	O(n)	Check every possible path between any two nodes in the tree
DFS Tree Diameter	O(n)	O(n)	Single DFS pass to find the longest path by treating it as tree diameter problem

Brute Force - All Pairs DFS — Algorithm Steps

Build adjacency list from parent array
For each pair of nodes, run DFS to find valid path
Track maximum valid path length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Convert parent array to adjacency list

Try All Pairs

For each pair (i,j), find valid path with DFS

Track Maximum

Keep track of longest valid path found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_N 100000

int graph[MAX_N][MAX_N];
int graphSize[MAX_N];
char s[MAX_N];
int maxPath;
int n;

void dfsPath(int start, int end, int current, bool* visited, int pathLen) {
    if (current == end) {
        if (pathLen > maxPath) {
            maxPath = pathLen;
        }
        return;
    }
    
    for (int i = 0; i < graphSize[current]; i++) {
        int neighbor = graph[current][i];
        if (!visited[neighbor] && s[current] != s[neighbor]) {
            visited[neighbor] = true;
            dfsPath(start, end, neighbor, visited, pathLen + 1);
            visited[neighbor] = false;
        }
    }
}

int solution(int* parent, char* str) {
    n = strlen(str);
    strcpy(s, str);
    
    if (n <= 1) return 1;
    
    // Initialize graph
    for (int i = 0; i < n; i++) {
        graphSize[i] = 0;
    }
    
    // Build adjacency list
    for (int i = 1; i < n; i++) {
        graph[parent[i]][graphSize[parent[i]]++] = i;
        graph[i][graphSize[i]++] = parent[i];
    }
    
    maxPath = 1;
    
    // Try all pairs of nodes
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            bool visited[MAX_N] = {false};
            visited[i] = true;
            dfsPath(i, j, i, visited, 1);
        }
    }
    
    return maxPath;
}

int main() {
    char line[200000];
    fgets(line, sizeof(line), stdin);
    
    // Parse parent array
    int parent[MAX_N];
    int count = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        parent[count++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    char s[MAX_N];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(parent, s);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) pairs of nodes, each requiring O(n) DFS traversal

⚠ Quadratic Growth

Space Complexity

O(n)

Adjacency list and DFS recursion stack

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - All Pairs DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler