JavaScript Challenge

Universal Lucky string:

Write a function(S) to find universal lucky string with following conditions-

1. All characters in S have the same exact frequency (i.e., occur the same number of times). For example, "aabbcc" is valid, but "baacddd" is not valid.

2. Deleting exactly 1 character from S will result in all its characters having the same frequency. For example, "aabbccc" and "aabbc" are valid because all their letters will have the same frequency if we remove occurrence of "c", but "aabbcccc" is not valid because we'd need to remove 2 characters.

@florin pop can you help me for this Js challenge?

Comments

[Matt Ellen-Tsivintzeli]

function lucky(s)
{
  // split the string into an array so that it can be reduced
  let sarr = s.split('');
  // reduce the array into a character -> count map
  let counts = sarr.reduce((acc, c) => {if(acc[c]){acc[c]++;}else{acc[c]=1;} return acc;}, {});
  let smallestCount = Number.MAX_VALUE;
  // find the smallest frequency in the map
  for(let c in counts)
  {
    if(Object.prototype.hasOwnProperty.call(counts, c) && counts[c] < smallestCount)
    {
        smallestCount = counts[c];
    }
  }
  let biggerCount = 0;
  // count how many characters exceed the smallest frequency
  for(let c in counts)
  {
    if(Object.prototype.hasOwnProperty.call(counts, c) && counts[c] > smallestCount)
    {
        biggerCount += counts[c] - smallestCount;
    }
  }

  // exceeding 0 times fullfills point 1
  let easyLucky = biggerCount == 0;
  // exceeding only once fullfills point 2
  let hardLucky = biggerCount == 1;
  // if either is true you have a lucky string
  return easyLucky || hardLucky;
}

Object.prototype.hasOwnProperty.call(counts, c) is necessary in case the prototype for object has been messed with.

[Matt Ellen-Tsivintzeli]

Also, I just found out about Map, so here's a version that uses that 😁:

function lucky(s)
{
  // split the string into an array so that it can be reduced
  let sarr = s.split('');
  // reduce the array into a character -> count map
  let counts = sarr.reduce((acc, c) => {
                                         if(acc.get(c))
                                         {
                                           acc.set(c, acc.get(c) + 1);
                                         }
                                         else
                                         {
                                           acc.set(c, 1);
                                         } 
                                         return acc;
                                       }, new Map());
  let smallestCount = Number.MAX_VALUE;
  // find the smallest frequency in the map
  counts.forEach((count, c) => {if(count < smallestCount){smallestCount = count;}});
  let biggerCount = 0;
  // count how many characters exceed the smallest frequency
  counts.forEach((count, c) => {if(count > smallestCount){biggerCount += count - smallestCount;}});
  // exceeding 0 times fullfills point 1
  let easyLucky = biggerCount == 0;
  // exceeding only once fullfills point 2
  let hardLucky = biggerCount == 1;
  // if either is true you have a lucky string
  return easyLucky || hardLucky;
}

[Avalander]

I know the header says "Javascript", but this is really easy in Haskell (or any language that has built-ins for sorting and grouping collections)

import Data.List (sort, group)

groupFrequencies :: String -> [[Int]]
groupFrequencies = group . sort . map length . group . sort

isLucky :: String -> Bool
isLucky x = length freqs == 1 || isAlmostLucky freqs
  where
    freqs = groupFrequencies x
    isAlmostLucky freqs = length freqs == 2 &&
                          length (last freqs) == 1 &&
                          head (head freqs) + 1 == head (last freqs)

The algorithm is as follows:

1. Sort the characters in the string: "abcabcb" -> "aabbbcc"
2. Group characters: "aabbbcc" -> [ "aa", "bbb", "cc" ]
3. Map outer list to length: [ "aa", "bbb", "cc" ] -> [ 2, 3, 2 ]
4. Sort and group again: [ 2, 3, 2 ] -> [[ 2, 2 ], [ 3 ]]

If the outer array has length of 1, all characters appear with the exact same frequency and we have a lucky string.

If the outer array has a length of 2, the second element has a length of 1, and the element in the second array is one higher than any element in the first array, we have an almost lucky string.

[Avalander]

Of course, we can just implement the same algorithm in Javascript, we just need to implement a group function. In this case, I have implemented it as a reducer function so that I can use it in an array method chain.

const last = arr => arr[arr.length - 1]

const appendToLast = (arr, x) => {
  const lastElement = last(arr)
  lastElement.push(x)
  return arr
}

const group = (prev, x) =>
  prev.length === 0
    ? [[ x ]]
    : last(prev)[0] === x
    ? appendToLast(prev, x)
    : [ ...prev, [ x ]]

// Everything above this line is because Javascript doesn't have group built in.

const length = arr => arr.length

const isAlmostLucky = groupedFreqs =>
  groupedFreqs.length === 2 &&
  groupedFreqs[1].length === 1 &&
  groupedFreqs[1][0] === groupedFreqs[0][0] + 1

const isLucky = str => {
  const groupedFreqs = str.split('')
    .sort()
    .reduce(group, [])
    .map(length)
    .sort()
    .reduce(group, [])
  return groupedFreqs.length === 1 ||
    isAlmostLucky(groupedFreqs)
}