Table of Contents

ExplanationImplementation

Official Editorial

Explanation

Define dp[i][j]\texttt{dp}[i][j] as the maximum frequency of character jj for node ii. Then, sort the nodes topographically in order to perform dynamic programming on the DAG. Our transition is simple:

dp[i][j]=max⁡dp[k][j]:k∈adj[i]\texttt{dp}[i][j] = \max \texttt{dp}[k][j] : k \in \texttt{adj}[i]

while also incrementing dp[i][l]\texttt{dp}[i][l] for the current node ii where ll represents sis_i, since we can pick up one more of this letter on our path.

Implementation

Time Complexity: O(N+M)\mathcal{O}(N + M)

C++

#include <bits/stdc++.h>


using namespace std;


int main() {
	int n, m;
	cin >> n >> m;
	string a;
	cin >> a;

Java

import java.io.*;
import java.util.*;


public class Substring {
 	Code Snippet: Kattio (Click to expand)
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int N = io.nextInt();
		int M = io.nextInt();
		char[] A = io.next().toCharArray();

Python

Warning!

Due to the tight time limit for Python, the following code receives a TLE verdict on PyPy 3 but receives AC on PyPy 3-64.

from collections import deque


n, m = map(int, input().split())
a = input()


adj = [[] for _ in range(n)]
in_degree = [0] * n
for _ in range(m):
	x, y = map(int, input().split())
	x -= 1

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum