<p>There is a <strong>directed graph</strong> of <code>n</code> colored nodes and <code>m</code> edges. The nodes are numbered from <code>0</code> to <code>n - 1</code>.</p>

<p>You are given a string <code>colors</code> where <code>colors[i]</code> is a lowercase English letter representing the <strong>color</strong> of the <code>i<sup>th</sup></code> node in this graph (<strong>0-indexed</strong>). You are also given a 2D array <code>edges</code> where <code>edges[j] = [a<sub>j</sub>, b<sub>j</sub>]</code> indicates that there is a <strong>directed edge</strong> from node <code>a<sub>j</sub></code> to node <code>b<sub>j</sub></code>.</p>

<p>A valid <strong>path</strong> in the graph is a sequence of nodes <code>x<sub>1</sub> -&gt; x<sub>2</sub> -&gt; x<sub>3</sub> -&gt; ... -&gt; x<sub>k</sub></code> such that there is a directed edge from <code>x<sub>i</sub></code> to <code>x<sub>i+1</sub></code> for every <code>1 &lt;= i &lt; k</code>. The <strong>color value</strong> of the path is the number of nodes that are colored the <strong>most frequently</strong> occurring color along that path.</p>

<p>Return <em>the <strong>largest color value</strong> of any valid path in the given graph, or </em><code>-1</code><em> if the graph contains a cycle</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/04/21/leet1.png" style="width: 400px; height: 182px;" /></p>

<pre>
<strong>Input:</strong> colors = &quot;abaca&quot;, edges = [[0,1],[0,2],[2,3],[3,4]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The path 0 -&gt; 2 -&gt; 3 -&gt; 4 contains 3 nodes that are colored <code>&quot;a&quot; (red in the above image)</code>.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/04/21/leet2.png" style="width: 85px; height: 85px;" /></p>

<pre>
<strong>Input:</strong> colors = &quot;a&quot;, edges = [[0,0]]
<strong>Output:</strong> -1
<strong>Explanation:</strong> There is a cycle from 0 to 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == colors.length</code></li>
	<li><code>m == edges.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= m &lt;= 10<sup>5</sup></code></li>
	<li><code>colors</code> consists of lowercase English letters.</li>
	<li><code>0 &lt;= a<sub>j</sub>, b<sub>j</sub>&nbsp;&lt; n</code></li>
</ul>
class Solution:
    # 30mins to find Time Limit Exceeded solution
    # Yesss, 57mins and I managed to find this

    # I made one initial mistake: I knew I had to identify cycles, but I wrote the slowest possible cycle detection algorithm
    # I should have gone for indegree detection
    # This gave me TLE, then I thoght it was my DP DFS
    # I changed the DP algorithm to use a more clever result state, but it was based of
    # some skimming I've done through the Editorial, maybe without a basic skimming I wasn't
    # going to be able to 
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        graph, indegree = self.get_adj_list(edges, len(colors))
        # for node in range(len(colors)):
            # if self.has_cycle(node, set(), graph): # this is too slow for cycle detection
                # return -1

        if self.check_cycle(indegree, graph):
            return -1

        best = 0
        memo = {}
        for node in range(len(colors)):
            best = max(best, self.dp(node, colors[node], colors, graph, memo))

        # graph is a DAG
        # we can run DP without fear now
        return best

    def dp(self, node, color, colors, graph, memo):
        key = (node, color)
        if key in memo:
            return memo[key]

        edges = graph.get(node, set())
        best = 0
        for e in edges:
            best = max(best, self.dp(e, color, colors, graph, memo))

        if color == colors[node]:
            best += 1

        memo[key] = best
        return memo[key]

    def has_cycle(self, node, stack, graph):
        if node in stack:
            return True
        stack.add(node)
        edges = graph.get(node, set())
        for e in edges:
            if self.has_cycle(e, stack, graph):
                return True
        stack.remove(node)
        return False
    
    def get_adj_list(self, edges, n):
        indegree = [0]*n
        graph = {}
        for e in edges:
            src, tgt = e[0], e[1]
            src_conn = graph.get(src, set())
            src_conn.add(tgt)
            graph[src] = src_conn
            indegree[tgt] += 1
        return graph, indegree
    
    def check_cycle(self, indegree, graph):
        q = []
        for node in range(len(indegree)):
            if indegree[node] == 0:
                q.append(node)

        while q:
            c = q.pop(0)
            edges = graph.get(c, set())
            for e in edges:
                indegree[e] -= 1
                if indegree[e] == 0:
                    q.append(e)

        return max(indegree) != 0

# this is a directed graph which means there could be cycles!
# cycle == -1, so not valid path

# color value is the color of the majority of the nodes in the path

# a valid path is a path from A -> X, without cycles!

# each node has a color
# if we start a path from each node, we should target its color?
# what would be the answer?
# we call a DFS for every node and give them a targeted color?
# we also have to represent the cycles somehow
# a path starting at node X can have a different stack state than a path
# calling node X


# 2 <-> 0 <-> 3 -> 4
# 2->3

# we gonna execute 0 first, then we get its result for the color it has
# 2 has the same color

# if there's a cycle then we return -1 for the problem!

# 1. run algorithm to identify cycle, if it has return -1
# 2. run DFS DP algo with state node,color. Starting from each node


# the optimization I thought was, instead of counting best result for target
# we count all the colors! and store in memo[node] = [x,y,z]
# but there are many possible paths! if we store one result table for each node
# it should be a result table for each possible n*e

# but we will keep 1 table for each node with 26 colors
# in this table we keep the BEST result for that color passing though that node
# we explore and get the table from the edge, then we compare edge_table[i] with node_table[i] and pick the best

# cycle detection seems slow
86665