Swap Lex Order - CodeSignal

Given a string str and an array of pairs that indicate which indices in the string can be swapped, the function solution(str, pairs) returns the lexicographically largest string that results from doing the allowed swaps. Indices can be swapped any number of times.

Example:

For str = "abdc" and pairs = [[1, 4], [3, 4]], the output should be solution(str, pairs) = "dbca".

By swapping the given indices, you get the strings: "cbda", "cbad", "dbac", "dbca". The lexicographically largest string in this list is "dbca".

Input/Output:

• Execution time limit: 4 seconds (py3)
• str: a string consisting only of lowercase English letters with guaranteed constraints of 1 ≤ str.length ≤ 104.
• pairs: an array containing pairs of indices that can be swapped in str (1-based). This means that for each pairs[i], you can swap elements in str that have the indices pairs[i][0] and pairs[i][1] with guaranteed constraints of 0 ≤ pairs.length ≤ 5000 and pairs[i].length = 2.
• output: a string.

Approach:

      

    1. Create a Adjancency list by iterating the array

    2. Then do a DFS for each of the vertex and get all the connected indices (Indices that can be swapped) and create a group

    3. Then for each of the group get the respective index elements and sort them is desceding order from the original string and place them one by one in a new string.

Code

from collections import defaultdict

def solution(str1, pairs):

edges = defaultdict(lambda : [])

for pair in pairs:

edges[pair[0]-1].append(pair[1]-1)

edges[pair[1]-1].append(pair[0]-1)

# 2. then do a DFS

def dfs_util(vertex, edges, visited):

visited.append(vertex)

for neigh in edges[vertex]:

if neigh not in visited:

dfs_util(neigh, edges, visited)

def dfs(vertex, edges):

visited = []

dfs_util(vertex, edges,visited)

return visited

groups = []

for vertex in edges.keys():

group = sorted(dfs(vertex, edges))

if group not in groups:

groups.append(group)

newStr = list(str1)

vertChars = []

for group in groups:

for vert in group:

vertChars.append(newStr[vert])

vertChars.sort()

vertChars.reverse()

for vert in group:

newStr[vert] = vertChars[0]

vertChars.pop(0)

return "".join(newStr)