ZeeshanAli-0704

Posted on

# Lexicographical Rank of String- Efficient Approach

``````// Max count is 256
let MAX_CHAR = 256;

// Calculating factorial of n
function fact(n) {
return n <= 1 ? 1 : n * fact(n - 1);
}

// Updating count table with count & clumative count

// example = "ABCK"
// for A = 1
// for B = 2 ( as before B we have A already appeared)
// for C = 3 ( as before C we have B & A (2+1) already appeared)
// For D = 3
// ...

// For K = 4 ( as before K we have A to J  out of which till C we have match in string & after 3 till J keeping count same.)

function populateAndIncreaseCount(count, str) {
let i;

for (i = 0; i < str.length; ++i) ++count[str[i].charCodeAt(0)];

for (i = 1; i < MAX_CHAR; ++i) count[i] += count[i - 1];

console.log(count);
}
// reducing as that Alphabet is now considered hence rest all // should run by -1;
function updatecount(count, ch) {
let i;
for (i = ch.charCodeAt(0); i < MAX_CHAR; ++i) --count[i];
}
function findRank(str) {
let len = str.length;
let mul = fact(len);
let rank = 1,
i;

let count = new Array(MAX_CHAR);
for (let i = 0; i < count.length; i++) {
count[i] = 0;
}

populateAndIncreaseCount(count, str);

for (i = 0; i < len; ++i) {
mul = Math.floor(mul / (len - i));
rank += count[str[i].charCodeAt(0) - 1] * mul;
updatecount(count, str[i]);
}

return rank;
}

console.log(findRank("DCCBA"));

``````