Katkat
Back

Minimize a String Using Allowed Swaps

PayPalSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of graph connectivity and constrained string reordering, along with proficiency in applying efficient data structures and algorithms for handling large inputs.

You are given a string s of lowercase English letters and an array pairs, where each element pairs[i] = [a, b] means you may swap the characters at indices a and b. You may perform any number of swaps, and each allowed pair may be used multiple times.

Return the lexicographically smallest string that can be obtained.

Indices are zero-based.

Example 1: Input: s = "dcab", pairs = [[0, 3], [1, 2]] Output: "bacd"

Example 2: Input: s = "dcab", pairs = [[0, 3], [1, 2], [0, 2]] Output: "abcd"

Constraints:

  • 1 <= s.length <= 100000
  • 0 <= pairs.length <= 100000
  • pairs[i].length == 2
  • 0 <= pairs[i][0], pairs[i][1] < s.length