1202-smallest-string-with-swaps

Try it on leetcode

Description

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

 

Example 1:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

Example 2:

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"

Example 3:

Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explaination: 
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"

 

Constraints:

• 1 <= s.length <= 10^5
• 0 <= pairs.length <= 10^5
• 0 <= pairs[i][0], pairs[i][1] < s.length
• s only contains lower case English letters.

Solution(Python)

class Solution:
    def __init__(self):
        self.N = 100001
        self.adj = [[] for _ in range(self.N)]
        self.visited = [False] * self.N

    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        return self.UnionFind_approach(s, pairs)

    # Time Complexity: O(E+Vlog(V))
    # Space Complexity: O(E+V)
    def dfs_approach(self, s: str, pairs: List[List[int]]) -> str:
        s = list(s)
        for edge in pairs:
            source = edge[0]
            destination = edge[1]

            self.adj[source].append(destination)
            self.adj[destination].append(source)

        for vertex in range(len(s)):
            if not self.visited[vertex]:
                characters = []
                indices = []
                self.dfs(s, vertex, characters, indices)

                characters.sort()
                indices.sort()

                for i in range(len(indices)):
                    s[indices[i]] = characters[i]
        return "".join(s)

    def dfs(self, s, vertex, characters, indices):
        characters.append(s[vertex])
        indices.append(vertex)

        self.visited[vertex] = True

        for adjacent in self.adj[vertex]:
            if not self.visited[adjacent]:
                self.dfs(s, adjacent, characters, indices)

    # Time Complexity: O((E+V).αV+VlogV)
    # Space Complexity: O(V)
    def UnionFind_approach(self, s: str, pairs: List[List[int]]) -> str:
        uf = UnionFind(len(s))
        s = list(s)
        for (source, dest) in pairs:
            uf.union(source, dest)

        hashmap = defaultdict(lambda: [])
        for v in range(len(s)):
            root = uf.find(v)
            hashmap[root].append(v)

        smallestString = [" "] * len(s)
        for component in hashmap:
            indices = hashmap[component]
            characters = [s[index] for index in indices]
            characters.sort()

            for i in range(len(indices)):
                smallestString[indices[i]] = characters[i]

        return "".join(smallestString)


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.root = [i for i in range(n)]
        self.rank = [0] * n

    # Time Complexity: O(αn)
    def find(self, a):
        while a != self.root[a]:
            a = self.root[a]
        return self.root[a]

    # Time Complexity: O(αn)
    def union(self, a, b):
        groupA = self.find(a)
        groupB = self.find(b)

        if groupA != groupB:
            if self.rank[groupA] >= self.rank[groupB]:
                self.root[groupB] = groupA
                self.rank[groupA] += 1
            elif self.rank[groupA] < self.rank[groupB]:
                self.root[groupA] = groupB
                self.rank[groupB] += 1

    def isconnected(self, a, b):
        return self.find(a) == self.find(b)