-
Notifications
You must be signed in to change notification settings - Fork 2
/
Result.java
67 lines (54 loc) · 1.99 KB
/
Result.java
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
package hackrank.algorithm.implement.bigger;
import java.util.ArrayList;
import java.util.List;
/**
* @see <a href="https://www.hackerrank.com/challenges/bigger-is-greater">Bigger is Greater</a>
*/
public class Result {
/**
* @param w word value
* @return Next lexicographically greater word directly following {@code w}. If a greater word does not exist,
* returns "no answer".
*/
public static String biggerIsGreater(String w) {
char[] characters = w.toCharArray();
for (int i = characters.length - 2; i >= 0; i--) {
if (hasGreaterAfter(i, characters)) {
return w.substring(0, i) + findGreaterAfter(i, characters);
}
}
return "no answer";
}
private static String findGreaterAfter(int index, char[] characters) {
char letter = characters[index];
List<Character> charsAfter = new ArrayList<>(characters.length);
for (int i = index; i < characters.length; i++) {
charsAfter.add(characters[i]);
}
// sort to impose increasing lexicographical order
charsAfter.sort(Character::compareTo);
char leadLetter = '-'; // guaranteed to be set by virtue of hasGreaterAfter() being true
for (int i = 0; i < charsAfter.size(); i++) {
if (charsAfter.get(i) > letter) {
leadLetter = charsAfter.get(i);
charsAfter.remove(i);
break;
}
}
StringBuilder sb = new StringBuilder();
sb.append(leadLetter);
for (char minOrderLetter : charsAfter) {
sb.append(minOrderLetter);
}
return sb.toString();
}
private static boolean hasGreaterAfter(int index, char[] characters) {
char max = characters[index + 1];
for (int i = index + 2; i < characters.length; i++) {
if (max < characters[i]) {
max = characters[i];
}
}
return max > characters[index];
}
}