Skip to content

Instantly share code, notes, and snippets.

@rohandalvi
Created November 29, 2019 10:12
Show Gist options
  • Save rohandalvi/c38bff31372cc6b27cbb8bb9637da06d to your computer and use it in GitHub Desktop.
Save rohandalvi/c38bff31372cc6b27cbb8bb9637da06d to your computer and use it in GitHub Desktop.
class Solution {
public String reorganizeString(String S) {
Character[] c = new Character[S.length()];
Map<Character, Integer> map = new HashMap<>();
for(int i = 0;i<S.length();i++) {
c[i] = S.charAt(i);
map.putIfAbsent(S.charAt(i), 0);
map.put(S.charAt(i), map.get(S.charAt(i))+1);
}
Arrays.sort(c, new Comparator<Character>(){
public int compare(Character c1, Character c2) {
int v1 = map.get(c1);
int v2 = map.get(c2);
if(v1 == v2) {
return c2 - c1;
} else {
return v2 - v1;
}
}
});
StringBuilder sb = new StringBuilder();
int start = 0;
int end = c.length-1;
int count = 0;
while(start<end) {
sb.append(c[start++]).append(c[end--]);
count+=2;
}
if(count<c.length) sb.append(c[start++]);
for(int i = 1; i<sb.toString().length()-1;i++) {
if(sb.charAt(i) == sb.charAt(i-1) || sb.charAt(i)==sb.charAt(i+1)) return "";
}
return sb.toString();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment