DEV Community

ZeeshanAli-0704
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"));

Enter fullscreen mode Exit fullscreen mode

Top comments (0)