Horje
Longest mutation sequence

Given a list of conversion tuples Arr[], such that string Arr[i][0] gets converted to string Arr[i][1]. A character is considered good if it has one-to-one mapping to some other character throughout all the conversions, for example during conversion of “abb” to “abc”, b->c is considered good. Your task is to find the longest chain of good characters in the form x->y->z… where x,y, and z are good characters.

Examples:

Input: {{‘ab’, ‘ac’}, {‘yz’, ‘xz’},{‘ee’, ‘ee’},{‘aaac’, ‘abag’},{‘g’, ‘h’}}
Output: {a, b, c, g, h}
Explanation:
tuple 1: b -> c.
tuple 2: y -> x.
tuple 3: no mutations occurred
tuple 4: a -> b, and c -> g
tuple 5: g -> h
the longest mutation sequence is [‘a->b->c->g->h’].

Input: { {“term”, “team”},{“drift”, “draft”}}
Output: { i, a }

Approach Using BFS:

The approach involves constructing a directed graph based on observed good conversions in the tuples, performing a modified BFS (Breadth-First Search) to traverse the graph, and updating the longest good chain, resulting in an efficient solution to identify the sequence of good character conversions.

Steps to solve the problem:

  • Create a graph and Initialize adj (adjacency list) and ind (in-degree array).
  • For each tuple in arr
    • Compare corresponding letters of the first and second words.
    • If different, update adj and ind based on the character changes.
  • Initialize a queue qu with nodes having in-degree 0.
  • Initialize variables ans (answer) and maxi (maximum chain length).
  • While qu is not empty:
    • Pop a node from qu.
    • Traverse the chain of good characters:
    • Add each letter to the ans.
    • Update maxi if the current chain is longer.
    • Push connected nodes with in-degree 0 to qu.
  • Print the longest good character chain stored in ans.

Below is the implementation of the approach:

C++

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
void longestGoodSequence(vector<pair<string, string> >& arr,
                         vector<int> adj[],
                         vector<int>& ind)
{
    // Initialize a queue with nodes having in-degree 0
    queue<int> q;
    for (int i = 0; i < 26; i++) {
        if (ind[i] == 0) {
            q.push(i);
        }
    }
    // Variables to store the answer
    vector<char> ans;
    ll maxi = 1;
    // Perform topological sort
    while (q.empty() == false) {
        vector<char> ans1;
        int for1 = q.front();
        q.pop();
        ans1.push_back(for1 + 'a');
 
        // Traverse the chain of mutations
        while (adj[for1].size() > 0) {
            ans1.push_back(adj[for1][0] + 'a');
            for1 = adj[for1][0];
        }
 
        // Update the answer if the current chain is longer
        if (ans1.size() > maxi) {
            maxi = ans1.size();
            ans = ans1;
        }
    }
 
    // Output the result
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
}
 
int main()
{
    // User-defined input for the tuples of words
    vector<pair<string, string> > arr
        = { { "ab", "ac" },
            { "yz", "xz" },
            { "ee", "ee" },
            { "aaac", "abag" },
            { "g", "h" } };
 
    // Create adjacency list and in-degree array
    vector<int> adj[26];
    vector<int> ind(26, 0);
 
    // Build the adjacency list and in-degree array
    for (int i = 0; i < arr.size(); i++) {
        ll len = arr[i].first.size();
        for (int j = 0; j < len; j++) {
            if (arr[i].first[j] != arr[i].second[j]) {
                ll val1 = arr[i].first[j] - 'a';
                ll val2 = arr[i].second[j] - 'a';
                ind[val2]++;
                adj[val1].push_back(val2);
            }
        }
    }
    longestGoodSequence(arr, adj, ind);
    return 0;
}

Java

import java.util.*;
 
public class GFG {
 
    public static void longestGoodSequence(List<Pair<String, String>> arr, List<Integer>[] adj, List<Integer> ind) {
        // Initialize a queue with nodes having in-degree 0
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < 26; i++) {
            if (ind.get(i) == 0) {
                q.add(i);
            }
        }
 
        // Variables to store the answer
        List<Character> ans = new ArrayList<>();
        long maxi = 1;
 
        // Perform topological sort
        while (!q.isEmpty()) {
            List<Character> ans1 = new ArrayList<>();
            int for1 = q.poll();
            ans1.add((char) (for1 + 'a'));
 
            // Traverse the chain of mutations
            while (!adj[for1].isEmpty()) {
                ans1.add((char) (adj[for1].get(0) + 'a'));
                for1 = adj[for1].get(0);
            }
 
            // Update the answer if the current chain is longer
            if (ans1.size() > maxi) {
                maxi = ans1.size();
                ans = new ArrayList<>(ans1);
            }
        }
 
        // Output the result
        for (char c : ans) {
            System.out.print(c + " ");
        }
    }
 
    public static void main(String[] args) {
        // User-defined input for the tuples of words
        List<Pair<String, String>> arr = Arrays.asList(
                new Pair<>("ab", "ac"),
                new Pair<>("yz", "xz"),
                new Pair<>("ee", "ee"),
                new Pair<>("aaac", "abag"),
                new Pair<>("g", "h")
        );
 
        // Create adjacency list and in-degree array
        List<Integer>[] adj = new ArrayList[26];
        for (int i = 0; i < 26; i++) {
            adj[i] = new ArrayList<>();
        }
 
        List<Integer> ind = new ArrayList<>(Collections.nCopies(26, 0));
 
        // Build the adjacency list and in-degree array
        for (Pair<String, String> pair : arr) {
            int len = pair.getFirst().length();
            for (int j = 0; j < len; j++) {
                if (pair.getFirst().charAt(j) != pair.getSecond().charAt(j)) {
                    int val1 = pair.getFirst().charAt(j) - 'a';
                    int val2 = pair.getSecond().charAt(j) - 'a';
                    ind.set(val2, ind.get(val2) + 1);
                    adj[val1].add(val2);
                }
            }
        }
 
        longestGoodSequence(arr, adj, ind);
    }
 
    static class Pair<K, V> {
        private K first;
        private V second;
 
        public Pair(K first, V second) {
            this.first = first;
            this.second = second;
        }
 
        public K getFirst() {
            return first;
        }
 
        public V getSecond() {
            return second;
        }
    }
}

Python3

from collections import deque
 
def longest_good_sequence(arr, adj, ind):
    # Initialize a queue with nodes having in-degree 0
    q = deque([i for i in range(26) if ind[i] == 0])
     
    # Variables to store the answer
    ans = []
    maxi = 1
     
    # Perform topological sort
    while q:
        ans1 = []
        for1 = q.popleft()
        ans1.append(chr(for1 + ord('a')))
 
        # Traverse the chain of mutations
        while adj[for1]:
            ans1.append(chr(adj[for1][0] + ord('a')))
            for1 = adj[for1].pop(0)
 
        # Update the answer if the current chain is longer
        if len(ans1) > maxi:
            maxi = len(ans1)
            ans = ans1
 
    # Output the result
    print(" ".join(ans))
 
if __name__ == "__main__":
    # User-defined input for the tuples of words
    arr = [
        ("ab", "ac"),
        ("yz", "xz"),
        ("ee", "ee"),
        ("aaac", "abag"),
        ("g", "h")
    ]
 
    # Create adjacency list and in-degree array
    adj = [[] for _ in range(26)]
    ind = [0] * 26
 
    # Build the adjacency list and in-degree array
    for tup in arr:
        for j in range(len(tup[0])):
            if tup[0][j] != tup[1][j]:
                val1 = ord(tup[0][j]) - ord('a')
                val2 = ord(tup[1][j]) - ord('a')
                ind[val2] += 1
                adj[val1].append(val2)
 
    longest_good_sequence(arr, adj, ind)

C#

using System;
using System.Collections.Generic;
 
public class GFG
{
    public static void LongestGoodSequence(List<Pair<string, string>> arr, List<int>[] adj, List<int> ind)
    {
        // Initialize a queue with nodes having in-degree 0
        Queue<int> q = new Queue<int>();
        for (int i = 0; i < 26; i++)
        {
            if (ind[i] == 0)
            {
                q.Enqueue(i);
            }
        }
 
        // Variables to store the answer
        List<char> ans = new List<char>();
        long maxi = 1;
 
        // Perform topological sort
        while (q.Count > 0)
        {
            List<char> ans1 = new List<char>();
            int for1 = q.Dequeue();
            ans1.Add((char)(for1 + 'a'));
 
            // Traverse the chain of mutations
            while (adj[for1].Count > 0)
            {
                ans1.Add((char)(adj[for1][0] + 'a'));
                for1 = adj[for1][0];
            }
 
            // Update the answer if the current chain is longer
            if (ans1.Count > maxi)
            {
                maxi = ans1.Count;
                ans = new List<char>(ans1);
            }
        }
 
        // Output the result
        foreach (char c in ans)
        {
            Console.Write(c + " ");
        }
    }
 
    public static void Main()
    {
        // User-defined input for the tuples of words
        List<Pair<string, string>> arr = new List<Pair<string, string>>
        {
            new Pair<string, string>("ab", "ac"),
            new Pair<string, string>("yz", "xz"),
            new Pair<string, string>("ee", "ee"),
            new Pair<string, string>("aaac", "abag"),
            new Pair<string, string>("g", "h")
        };
 
        // Create adjacency list and in-degree array
        List<int>[] adj = new List<int>[26];
        for (int i = 0; i < 26; i++)
        {
            adj[i] = new List<int>();
        }
 
        List<int> ind = new List<int>(new int[26]);
 
        // Build the adjacency list and in-degree array
        foreach (var pair in arr)
        {
            int len = pair.First.Length;
            for (int j = 0; j < len; j++)
            {
                if (pair.First[j] != pair.Second[j])
                {
                    int val1 = pair.First[j] - 'a';
                    int val2 = pair.Second[j] - 'a';
                    ind[val2]++;
                    adj[val1].Add(val2);
                }
            }
        }
 
        LongestGoodSequence(arr, adj, ind);
    }
 
    public class Pair<K, V>
    {
        private K first;
        private V second;
 
        public Pair(K first, V second)
        {
            this.first = first;
            this.second = second;
        }
 
        public K First { get { return first; } }
 
        public V Second { get { return second; } }
    }
}

Javascript

<script>
 
// Function to find the longest good sequence
function longestGoodSequence(arr, adj, ind) {
    let q = []; // Initialize an empty queue for nodes with in-degree 0
 
    // Loop to add nodes with in-degree 0 to the queue
    for (let i = 0; i < 26; i++) {
        if (ind[i] === 0) {
            q.push(i);
        }
    }
 
    let ans = []; // Array to store the answer
    let maxi = 1; // Variable to keep track of the maximum length found
 
    // Loop until the queue is empty
    while (q.length > 0) {
        let ans1 = []; // Temporary array to store the current sequence
        let for1 = q.shift(); // Remove and get the first element of the queue
        ans1.push(String.fromCharCode(for1 + 'a'.charCodeAt(0))); // Convert the number to its corresponding character and add to the sequence
 
        // Loop to traverse the chain of mutations
        while (adj[for1].length > 0) {
            ans1.push(String.fromCharCode(adj[for1][0] + 'a'.charCodeAt(0)));
            for1 = adj[for1].shift(); // Move to the next mutation in the chain
        }
 
        // If the current sequence is longer than the maximum found so far, update the answer
        if (ans1.length > maxi) {
            maxi = ans1.length;
            ans = ans1.slice(); // Copy the current sequence to the answer
        }
    }
 
    // Output the answer
    console.log(ans.join(" "));
}
 
function main() {
    // User-defined input for the tuples of words
    let arr = [
        ["ab", "ac"],
        ["yz", "xz"],
        ["ee", "ee"],
        ["aaac", "abag"],
        ["g", "h"]
    ];
 
    // Create adjacency list and in-degree array
    let adj = Array.from({length: 26}, () => []);
    let ind = new Array(26).fill(0);
 
    // Build the adjacency list and in-degree array based on the input
    arr.forEach(pair => {
        let len = pair[0].length;
        for (let j = 0; j < len; j++) {
            if (pair[0].charAt(j) !== pair[1].charAt(j)) {
                let val1 = pair[0].charCodeAt(j) - 'a'.charCodeAt(0);
                let val2 = pair[1].charCodeAt(j) - 'a'.charCodeAt(0);
                ind[val2]++; // Increment in-degree for the destination node
                adj[val1].push(val2); // Add an edge from the source node to the destination node
            }
        }
    });
 
    longestGoodSequence(arr, adj, ind); // Call the function to find and print the longest good sequence
}
 
main(); // Entry point of the program
 
 
</script>

Output

a b c g h

Time Complexity: O(N * M), where N is the number of tuples and M is the maximum length of words in a tuple
Auxiliary Space: O(N + M).


 


Reffered: https://www.geeksforgeeks.org

Android

Related
Rearrange array A[] in non-decreasing order by Swapping A[i] and C[j] if and only if B[i] equals to D[j] Rearrange array A[] in non-decreasing order by Swapping A[i] and C[j] if and only if B[i] equals to D[j]
How to Become a Flutter Developer - A Complete Roadmap [2024] How to Become a Flutter Developer - A Complete Roadmap [2024]
Find the string of length N according to the given conditions Find the string of length N according to the given conditions
How To Clear DNS Cache on Android Device? How To Clear DNS Cache on Android Device?
How to Build Live Train Status App in Android? How to Build Live Train Status App in Android?

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje