Lexicographically Smallest Equivalent String - Leetcode Solution

Problem Statement:

Given two strings A and B of equal length, we need to find the lexicographically smallest string C which has the same character set as A and B and is equivalent to A and B.

Solution:

The problem states that the strings A and B have the same length and we need to find the lexicographically smallest equivalent string with the same character set as A and B. So, we can apply a graph-based approach to solve this problem.

The basic idea is to create a graph using the characters in the strings A and B as nodes and the equivalent characters in the strings A and B as edges. Then we can perform a Depth-First Search (DFS) on the graph to find the lexicographically smallest equivalent string.

Algorithm:

1. Create an adjacency list for the characters in strings A and B. Each node in the adjacency list will contain a list of equivalent characters.

2. Traverse the adjacency list and perform a DFS on each unvisited node to find all the connected components.

3. For each connected component, sort the characters lexicographically and replace all the nodes with the lexicographically smallest node.

4. Finally, construct the equivalent string using the updated adjacency list.

Pseudo Code:

1. Initialize a visited array for all the characters in A and B.

2. Initialize an adjacency list for all the characters in A and B.

3. Populate the adjacency list with the equivalent characters from A and B. For each character in A and B, add the corresponding character from both strings to the adjacency list.

4. DFS on each unvisited node:

   • Mark the node as visited.
   • If the node has any equivalent nodes, perform DFS on each of them.
   • For each equivalent node, mark it as visited and add it to the connected component.
   • Update the connected component with the lexicographically smallest node.

5. Once all the connected components have been updated, construct the equivalent string:

   • For each character in A, find the corresponding node in the adjacency list and add the lexicographically smallest character to the result string.

Time Complexity:

The time complexity of this algorithm is O(n log n) where n is the length of the strings A and B. The DFS will be performed at most n times, and each DFS will take O(log n) time to sort the characters in the connected component.

Space Complexity:

The space complexity of this algorithm is O(n) to store the adjacency list and visited array.

Implementation:

Here is the Python implementation of the above algorithm:

class Solution: def smallestEquivalentString(self, A: str, B: str, S: str) -> str: # Initialize visited array for all the characters in A and B. visited = [False] * 26

    # Initialize adjacency list for all the characters in A and B.
    adj_list = [[] for _ in range(26)]
    
    # Populate the adjacency list with the equivalent characters from A and B.
    for i in range(len(A)):
        x = ord(A[i]) - ord('a')
        y = ord(B[i]) - ord('a')
        adj_list[x].append(y)
        adj_list[y].append(x)
    
    # DFS on each unvisited node.
    def dfs(node, component):
        visited[node] = True
        component.append(node)
        for neighbor in adj_list[node]:
            if not visited[neighbor]:
                dfs(neighbor, component)
    
    # For each connected component, sort the characters lexicographically and replace all the nodes with the lexicographically smallest node.
    for i in range(26):
        if not visited[i]:
            component = []
            dfs(i, component)
            min_char = min(component)
            for node in component:
                visited[node] = True
                adj_list[node] = min_char
    
    # Construct the equivalent string using the updated adjacency list.
    result = ""
    for char in S:
        result += chr(ord('a') + adj_list[ord(char) - ord('a')])
    
    return result

Input: A = "parker", B = "morris", S = "parser"

Output: "paakar"

1