Skip to content

Instantly share code, notes, and snippets.

@dfparker2002
Forked from alexislagante/nextLex.js
Created September 6, 2016 09:48
Show Gist options
  • Save dfparker2002/a8e82d47db805ca7956d3658759e36a5 to your computer and use it in GitHub Desktop.
Save dfparker2002/a8e82d47db805ca7956d3658759e36a5 to your computer and use it in GitHub Desktop.
Next String (using counting sort)
function nextLex(str) {
var breakIndex = -1;
var chars = str.split("");
for (var i=chars.length-1; i>0; i--) {
if (chars[i] > chars[i-1]) {
breakIndex = i-1;
break;
}
}
if (breakIndex > -1) {
var swapIndex = breakIndex + 1;
for (var i=swapIndex+1; i<chars.length; i++) {
if (chars[i] > str[breakIndex] && chars[i] < chars[swapIndex]) {
swapIndex = i;
}
}
swap(breakIndex, swapIndex, chars);
chars = countingSort(chars, breakIndex+1, chars.length-1);
}
return chars.join("");
}
function countingSort(array, start, end) {
var b = [];
for (var i=0;i<26;i++) {
b.push(0);
}
var aCode = 'a'.charCodeAt(0);
for (var i=start; i<=end; i++) {
var idx = (array[i].charCodeAt(0) - aCode)%26;
b[idx]++;
}
var right = [];
for (var i=0;i<b.length;i++){
var x = b[i];
while (x>0){
right.push(String.fromCharCode(aCode+i));
x--;
}
}
array.splice(start);
array = array.concat(right);
return array;
}
function swap(i, j, array) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
nextLex("xyzafedcb");
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment