Given a directed graph with N nodes and M edges. Each node is associated with lowercase english alphabet. Beauty of a path is defined as the number of most frequently occurring alphabet. Find the most beautiful path and return the maximum beauty value it has.

**CONSTRAINTS:**

1 < N,M < 300000

**FUNCTION DESCRIPTION: **

Complete the function beauty in code. Function must Return an integer, the beauty of most beautiful path. If the value is very large return -1.

Function beauty has the following parameter(s):

n: integer, number of nodes

m: integer, number of directed edges

S: string of length n where ith alphabet denotes the alphabets associated with ith node

X: list of length m

Y: list of length m

Source: Windows Questions C++

## 2 thoughts on - Is there any solution to find beautiful path by given information? [closed]

Someone please reply!!

#include

using namespace std;

const int maxn = 300011;

char s[maxn];

int deg[maxn], d[maxn];

vector w[maxn];

int Find(int u, int c) {

if (d[u] != -1) return d[u];

d[u] = 0;

for (int v : w[u]) {

d[u] = max(d[u], Find(v, c));

}

d[u] += (s[u] == c + ‘a’);

return d[u];

}

int main() {

int n, m;

scanf(“%d%d”, &n, &m);

scanf(“%s”, s + 1);

for (int i = 1; i <= m; ++i) {

int u, v;

scanf("%d%d", &u, &v);

w[u].push_back(v);

++deg[v];

}

int ct = 0;

queue que;

for (int i = 1; i <= n; ++i) {

if (!deg[i])

que.push(i), ++ct;

}

while (!que.empty()) {

int u = que.front();

que.pop();

for (int v : w[u]) {

if (–deg[v] == 0)

que.push(v), ++ct;

}

}

if (ct < n) {

puts("-1");

} else {

int ans = 0;

for (int c = 0; c < 26; ++c) {

memset(d, 0xff, sizeof d);

for (int i = 1; i <= n; ++i)

ans = max(ans, Find(i, c));

}

printf("%d\n", ans);

}

return 0;

}