hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Longest Path With Different Adjacent Characters
Problem: 2246. Longest Path With Different Adjacent Characters
Problem Link: https://leetcode.com/problems/longest-path-with-different-adjacent-characters/
Companies Asked: Microsoft, Hudson River Trading
Approach:
The problem is said to find the longest path through the nodes of the given tree where no two adjacent nodes will have the same character.
It is pretty easy to find the adjacency condition. Because standing on a node when we will try to access the child we can compare corresponding characters.
For a node, we have to -
Check if any of the children have the same character.
Set the acquired length as 0 for the path where the characters are the same.
Otherwise, keep going until we reach the leaf node.
Build the graph by adding edges between each i and parent[i].
Start running a DFS from node 0.
Access and traverse all the adjacent children. And run DFS for them as well.
When having the traversed length for a node, check if the character of the Parent and Child node is equal.
If equal then set the traversed_length as 0.
As we can acquire the maximum length from any of the sub-tree, we need to find the two acquired maximum lengths among children.
Add both maximum lengths acquired from children and take the maximum from running lengths.
Return maximum between two maximum acquired lengths.
The returned length will be used for finding out the most lengthy routes.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(N) + Stack
Code [C++]
class Solution {
public:
int solve(int node, vector<vector<int>>&graph, int parent, int & answerLength, string & assigned){
int maxOne = 0, maxTwo = 0;
for(int i=0; i<graph[node].size(); i++){
int child = graph[node][i];
if(child == parent) continue;
int length = solve(child, graph, node, answerLength, assigned);
length = (assigned[node] == assigned[child]) ? 0 : length + 1;
if(length >= maxTwo){
maxOne = maxTwo, maxTwo = length;
}
else if(length >= maxOne){
maxOne = length;
}
}
answerLength = max(answerLength, maxOne + maxTwo);
return max(maxOne, maxTwo);
}
int longestPath(vector<int>& parent, string s) {
int n = parent.size();
vector<vector<int>>graph(n);
for(int i=0; i<n; i++){
if(parent[i] != -1){
graph[parent[i]].push_back(i);
// graph[i].push_back(parent[i]);
}
}
int answerLength = 0;
solve(0, graph, 0, answerLength, s);
return answerLength + 1;
}
};