Задача: 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 {
    function smallestStringWithSwaps($s, $pairs) {
        $n = strlen($s);
        $adj = array_fill(0, $n, []);
        foreach ($pairs as $pair) {
            $adj[$pair[0]][] = $pair[1];
            $adj[$pair[1]][] = $pair[0];
        }

        $visited = array_fill(0, $n, false);
        $sArray = str_split($s);

        function dfs($node, &$adj, &$visited, &$sArray, &$indices, &$chars) {
            $visited[$node] = true;
            $indices[] = $node;
            $chars[] = $sArray[$node];
            foreach ($adj[$node] as $neighbor) {
                if (!$visited[$neighbor]) {
                    dfs($neighbor, $adj, $visited, $sArray, $indices, $chars);
                }
            }
        }

        for ($i = 0; $i < $n; $i++) {
            if (!$visited[$i]) {
                $indices = [];
                $chars = [];
                dfs($i, $adj, $visited, $sArray, $indices, $chars);
                sort($indices);
                sort($chars);
                for ($j = 0; $j < count($indices); $j++) {
                    $sArray[$indices[$j]] = $chars[$j];
                }
            }
        }

        return implode('', $sArray);
    }
}

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