master
1<<-DOC
2Given a string str and array of pairs that indicates which indices in the string can be swapped,
3return the lexicographically largest string that results from doing the allowed swaps.
4You can swap indices any number of times.
5
6Example
7
8For str = "abdc" and pairs = [[1, 4], [3, 4]], the output should be
9swapLexOrder(str, pairs) = "dbca".
10
11By swapping the given indices, you get the strings:
12"cbda", "cbad", "dbac", "dbca".
13The lexicographically largest string in this list is "dbca".
14
15Input/Output
16
17[time limit] 4000ms (rb)
18[input] string str
19
20A string consisting only of lowercase English letters.
21
22Guaranteed constraints:
231 ≤ str.length ≤ 104.
24
25[input] array.array.integer pairs
26
27An 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].
28
29Guaranteed constraints:
300 ≤ pairs.length ≤ 5000,
31pairs[i].length = 2.
32
33[output] string
34
35https://www.careercup.com/question?id=5652404478410752
36DOC
37
38describe "swap_lex_order" do
39 def swap_lex_order(string, pairs)
40 queue = [string]
41 max_node = string
42 computed_max = string.chars.sort.reverse.join
43
44 visited = {}
45 until queue.empty?
46 node = queue.shift
47 next if visited.key?(node)
48 return node if node == computed_max
49
50 if (node <=> max_node) > 0
51 max_node = node
52 end
53 visited[node] = true
54
55 pairs.each do |pair|
56 x, y = node[pair[0] - 1], node[pair[1] - 1]
57 duplicate = node.dup
58 duplicate[pair[1] - 1] = x
59 duplicate[pair[0] - 1] = y
60 queue.push(duplicate) unless visited.key?(duplicate)
61 end
62 end
63 max_node
64 end
65
66 def connected?(x, y)
67 (x & y).size > 0
68 end
69
70 def union(x, y)
71 (x + y).sort.uniq
72 end
73
74 def sort(pairs)
75 pairs.map(&:sort).sort { |x, y| (x[0] <=> y[0]) + (x[1] <=> y[1]) }
76 end
77
78 def connected_components_in(pairs)
79 pairs = sort(pairs)
80 connections = []
81 connections.push(pairs.pop) if pairs.size > 0
82
83 until pairs.empty?
84 pair = pairs.pop
85 connected = false
86 connected_at = nil
87 connections.size.times do |n|
88 connection = connections[n]
89 next if connection.nil?
90 next if connection.first > pair[1]
91 next if connection.last < pair[0]
92
93 if connected?(pair, connection)
94 if connected
95 connections[connected_at] = union(connections[connected_at], connection + pair)
96 connections[n] = nil
97 else
98 connections[n] = union(pair, connection)
99 connected = true
100 connected_at = n
101 end
102 end
103 end
104 connections.push(pair.sort) unless connected
105 end
106 connections.compact.map { |x| x.uniq }
107 end
108
109 def swap_lex_order(string, pairs)
110 connections = connected_components_in(pairs)
111 result = string.dup
112 connections.each do |connection|
113 letters = connection.map { |x| string[x - 1] }.sort { |x, y| y <=> x }
114 connection.each { |index| result[index - 1] = letters.shift }
115 end
116 result
117 end
118
119 def swap_lex_order(items, pairs)
120 0.upto(pairs.size - 1) do |i|
121 x = pairs[i]
122 (i + 1).upto(pairs.size - 1) do |j|
123 y = pairs[j]
124 if connected?(x, y)
125 pairs[j] = union(x, y)
126 x.clear
127 end
128 end
129 end
130
131 pairs.reject(&:empty?).each do |connection|
132 connection.sort!
133 candidates = connection.map { |x| items[x - 1] }.sort { |x, y| y <=> x }
134 connection.each_with_index { |x, i| items[x - 1] = candidates[i] }
135 end
136 items
137 end
138
139 [
140 { pairs: [[1, 4], [3, 4]], expected: [[1, 3, 4]] },
141 { pairs: [[1, 4], [7, 8]], expected: [[1, 4], [7, 8]] },
142 { pairs: [[1, 3], [6, 8], [3, 8], [2, 7]], expected: [[1, 3, 6, 8], [2, 7]] },
143 { pairs: [], expected: [] },
144 { pairs: [[1,2], [3,4], [6,5], [8,10]], expected: [[1, 2], [3, 4], [5, 6], [8, 10]] },
145 { pairs: [[8,5], [10,8], [4,18], [20,12], [5,2], [17,2], [13,25], [29,12], [22,2], [17,11]], expected: [[2, 5, 8, 10, 11, 17, 22], [4, 18], [12, 20, 29], [13, 25]]
146 },
147 ].each do |x|
148 it do
149 expect(connected_components_in(x[:pairs])).to match_array(x[:expected])
150 end
151 end
152
153 [
154 { str: "abdcegeh", pairs: [[1,2], [3,4], [5, 6], [2, 4], [6, 8]], expected: "dcbahgee" },
155 { str: "abdc", pairs: [[1,4], [3,4]], expected: "dbca" },
156 { str: "abcdefgh", pairs: [[1,4], [7,8]], expected: "dbcaefhg" },
157 { str: "acxrabdz", pairs: [[1,3], [6,8], [3,8], [2,7]], expected: "zdxrabca" },
158 { str: "z", pairs: [], expected: "z" },
159 { str: "dznsxamwoj", pairs: [[1,2], [3,4], [6,5], [8,10]], expected:"zdsnxamwoj" },
160 { str: "fixmfbhyutghwbyezkveyameoamqoi", pairs: [[8,5], [10,8], [4,18], [20,12], [5,2], [17,2], [13,25], [29,12], [22,2], [17,11]], expected: "fzxmybhtuigowbyefkvhyameoamqei" },
161 { str: "lvvyfrbhgiyexoirhunnuejzhesylojwbyatfkrv", pairs: [[13,23], [13,28], [15,20], [24,29], [6,7], [3,4], [21,30], [2,13], [12,15], [19,23], [10,19], [13,14], [6,16], [17,25], [6,21], [17,26], [5,6], [12,24]], expected: "lyyvurrhgxyzvonohunlfejihesiebjwbyatfkrv" },
162 { str: "a", pairs: [], expected: "a" },
163 ].each do |x|
164 it do
165 result = swap_lex_order(x[:str], x[:pairs])
166 expect(result).to eql(x[:expected])
167 end
168 end
169end