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