Longest Colored Path

Problem Overview

The tree nodes are colored red or blue, and a valid path is either one color the whole way or a single red stretch joined to a single blue stretch.

Intuition

The tree nodes are colored red or blue, and a valid path is either one color the whole way or a single red stretch joined to a single blue stretch. Nodes of the same color that stay connected through that color form a tree of their own. Inside a tree, two breadth first searches from the ends of a diameter give every node its longest same color distance. A red blue edge can then attach those two arms. The answer is the number of nodes on the best path.

Algorithm

1Build the undirected tree. Edge endpoints in the input are 1 indexed, so subtract one before linking them.
2Explore each same color component on its own. A search from any node finds one end of that component, and a second search from that end finds the other end together with the distances to it.
3A third search from the opposite end fills the remaining distances. Each node keeps the larger of the two, which is how far it can reach while staying on its own color.
4The one color answer for the component is one more than the distance between the two ends, because the score counts nodes.
5For every edge whose endpoints have different colors, add the two same color reaches and then add two for the endpoints of that edge. Keep the maximum.

Example Walkthrough

Input: s = "RBBRR", edges = [[1,2],[2,3],[2,4],[4,5]]

1. Node 1 is red. Nodes 2 and 3 are blue. Nodes 4 and 5 are red.
2. The longest blue path is nodes 3 and 2. The longest all red path is nodes 4 and 5.
3. The edge between 2 and 4 joins those arms into the path 3, 2, 4, 5.

Output: 4

Common Pitfalls

• The score counts nodes. An edge distance of d covers d + 1 nodes.
• A path may change color only once. Red, then blue, then red is two changes and is not allowed.
• Same color nodes in different parts of the tree are separate components when no same color edge connects them.
• Edges are 1 indexed. Using them as array indexes without subtracting one walks off the color string.

Longest Colored Path.java

Java

// Approach: A valid path is one color, or one red run joined to one blue run.
// Same-color nodes form tree components. In a tree the farthest node from
// anywhere is an endpoint of a diameter, so two BFS passes give every node's
// longest same-color distance. A bichromatic edge then joins those two arms.
// Complexity: O(n) time, O(n) extra space.
import java.util.*;

class Solution {
    public int longestPath(String s, int[][] edges) {
        int n = s.length();
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++)
            adj[i] = new ArrayList<>();
        for (int[] e : edges) {
            int u = e[0] - 1;
            int v = e[1] - 1;
            adj[u].add(v);
            adj[v].add(u);
        }

        int[] distA = new int[n];
        int[] distB = new int[n];
        int[] far = new int[n];
        Arrays.fill(distA, -1);
        Arrays.fill(distB, -1);
        boolean[] seen = new boolean[n];
        int best = 0;

        for (int src = 0; src < n; src++) {
            if (seen[src])
                continue;
            char col = s.charAt(src);
            List<Integer> comp = new ArrayList<>();
            int endA = bfs(src, col, s, adj, distA, comp);
            for (int node : comp) {
                seen[node] = true;
                distA[node] = -1;
            }

            List<Integer> touched = new ArrayList<>();
            int endB = bfs(endA, col, s, adj, distA, touched);
            bfs(endB, col, s, adj, distB, new ArrayList<>());

            best = Math.max(best, distA[endB] + 1);
            for (int node : comp) {
                far[node] = Math.max(distA[node], distB[node]);
                distA[node] = -1;
                distB[node] = -1;
            }
        }

        for (int[] e : edges) {
            int u = e[0] - 1;
            int v = e[1] - 1;
            if (s.charAt(u) != s.charAt(v))
                best = Math.max(best, far[u] + far[v] + 2);
        }
        return best;
    }

    // Fills dist for the same-color component and returns a farthest node.
    private int bfs(int start, char col, String s, List<Integer>[] adj, int[] dist, List<Integer> touched) {
        ArrayDeque<Integer> q = new ArrayDeque<>();
        dist[start] = 0;
        q.add(start);
        touched.add(start);
        int farNode = start;

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj[u]) {
                if (s.charAt(v) != col || dist[v] != -1)
                    continue;
                dist[v] = dist[u] + 1;
                touched.add(v);
                q.add(v);
                if (dist[v] > dist[farNode])
                    farNode = v;
            }
        }
        return farNode;
    }
}

Was this solution helpful?