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

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]

• Harsh says:

Someone please reply!!

• Dkshash says:

#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;
}