How to match and group strings efficiently in Javascript?

Question

Write a function that returns an integer indicating number of times a group of string "pzmcb" appears in a string in no particualr orther. for example input string 1 -> "abdpsclmhz" output 1 -> 1 input string 2 : pzmcbcbpzmpcm output 2: 2

I have written the code but it is not efficient and cannot handle large input string. I will appreciate it if an efficent way of writing this function can be provided

'use strict';

//pmzcbpmzcbpmz  [0 -4] [5 - 9] returns 2

function matchGroup(word) {
    let regex = /[pzmcb]/g
  let stringArray = word.match(regex);

  //console.log(stringArray);
  let cloneArray = [...stringArray];
  let stored = [];
  let searchString = "";
  let secondString = "";
  let temp = "";
    let tempArray = [];

  stringArray.forEach(item => {
    if (cloneArray.indexOf(item) >= 0 && searchString.indexOf(item) === -1) {
        searchString += item;
        if (searchString.length === 5) {
          stored.push(searchString);
          searchString = "";
        }
    } else if(secondString.indexOf(item) === -1){
        secondString += item;
      if (secondString.length === 5) {
          stored.push(searchString);
          secondString = "";
        }
    }else {
       temp += item;
      if (temp.length === 5) {
          tempArray.push(temp);
          temp = "";
      }
    }
});

    return stored.length;
// return integer
}


var paragraph = 'pzmcbpdfbcmz';
let result = matchGroup("abcdefpfklmhgzpzmcbpdfbcmzjklmoplzdsaklmcxheqgexcmpzdhgiwqertyhgdsbnmkjilopazxcsdertijuhgbdmlpoiqarstiguzcmnbgpoimhrwqasfgdhuetiopmngbczxsgreqad");
console.log(result);

I expect that the matchGroup function to return exact integers for large inputs

What about overlapping substrings? For example, how many times does "aba" appear in "ababa" ? — גלעד ברקן, Aug 02 '19 at 17:28
@MrSmith42 is a constant string that we want to match but it can be in any particular order .e.g czpmb should return a match of 1. — Jimi Hunter, Aug 04 '19 at 10:11
@גלעדברקן "aba" my case is not for repeating characters. however lets say ab is a group to be matched then ababa should return 2 from the function — Jimi Hunter, Aug 04 '19 at 10:15

score 0 · Answer 1 · answered Aug 02 '19 at 19:27

function countChar(char, string) {
    return (string.match(new RegExp(char, "g")) || []).length;
}

function countDistinctSubstring(sub, string) {
    firstChars = {};
    for (i = 0; i < sub.length; i++) {
        if (sub[i] in firstChars)
            firstChars[sub[i]]++;
        else
            firstChars[sub[i]] = 1;
    }
    return Math.min(...Object.keys(firstChars).map(key => Math.floor(countChar(key, string) / firstChars[key])));
}

> countDistinctSubstring("pzmcb", "abdpsclmhz");
< 1
> countDistinctSubstring("pzmcb", "pzmcbcbpzmpcm");
< 2
> countDistinctSubstring("pzmcbpdfbcmz", "abcdefpfklmhgzpzmcbpdfbcmzjklmoplzdsaklmcxheqgexcmpzdhgiwqertyhgdsbnmkjilopazxcsdertijuhgbdmlpoiqarstiguzcmnbgpoimhrwqasfgdhuetiopmngbczxsgreqad");
< 3

I can't tell for sure, but I think this is what you are looking for. It counts the number of occurrences of each letter in the small string, then finds the minimum ratio of occurrences in the large string to those in the small string for each character. This minimum ratio is the maximum number of distinct times the small string can be composed of letters from the larger one.

Note that this answer was used in making the countChar function.

score 0 · Accepted Answer · answered Aug 04 '19 at 10:45

I'd build up a map of character counts:

   function countChars(str) {
     const count = {};
     for(const char of str) count[char] = (count[char] || 0) + 1;
     return count;
  }

Now we can easily build up count maps of the string to find and the source:

   const toFind = countChars("pzmbc"),
      source = countChars("pzmcbpdfbcmz");

Now we can find the smallest relationship of chars to find and chars that are there:

  const result = Math.min(
     ...Object.entries(toFind).map(([char, need]) => Math.floor((source[char] || 0) / need))
  );

How to match and group strings efficiently in Javascript?

2 Answers2