Задача: 1202. Smallest String With Swaps
Сложность: medium

Вам дана строка s и массив пар индексов в строке pairs, где pairs[i] = [a, b] указывает на 2 индекса (начиная с 0) в строке.
Вы можете менять местами символы в любой паре индексов в заданных парах любое количество раз.
Верните лексикографически наименьшую строку, которую можно получить после выполнения перестановок.

Пример:

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"

👨‍💻 Алгоритм:

1⃣Создание списка смежности:
Итеративно пройдитесь по парам и создайте список смежности adj, где adj[source] содержит все смежные вершины вершины source.

2⃣Обход графа и сбор индексов и символов:
Итеративно пройдитесь по индексам от 0 до s.size() - 1. Для каждого индекса vertex:
- выполните DFS, если вершина еще не посещена (visited[vertex] = false).
- во время выполнения DFS сохраняйте vertex в список indices и символ s[vertex] в список characters.

3⃣Сортировка и построение результирующей строки:
Отсортируйте списки indices и characters.
Пройдитесь по индексам и символам, и разместите i-й символ в i-й индекс результирующей строки smallestString.
Верните smallestString.

😎 Решение:

class Solution {
    func smallestStringWithSwaps(_ s: String, _ pairs: [[Int]]) -> String {
        var adj = Array(repeating: [Int](), count: s.count)
        for pair in pairs {
            adj[pair[0]].append(pair[1])
            adj[pair[1]].append(pair[0])
        }
        
        var visited = Array(repeating: false, count: s.count)
        var sArray = Array(s)
        
        func dfs(_ node: Int, _ indices: inout [Int], _ chars: inout [Character]) {
            visited[node] = true
            indices.append(node)
            chars.append(sArray[node])
            for neighbor in adj[node] {
                if !visited[neighbor] {
                    dfs(neighbor, &indices, &chars)
                }
            }
        }
        
        for i in 0..<s.count {
            if !visited[i] {
                var indices = [Int]()
                var chars = [Character]()
                dfs(i, &indices, &chars)
                indices.sort()
                chars.sort()
                for (index, char) in zip(indices, chars) {
                    sArray[index] = char
                }
            }
        }
        
        return String(sArray)
    }
}

Ставь 👍 и забирай 📚 Базу знаний