CODEWITHSUNDEEP
javascriptdata-structures
Akash
Akash

Reputation: 69

Is string subsequence of another. Solution not accepted, but runs fine in my IDE

I'm learning JavaScript and was working on some DSA problems. Here is the one I am trying to solve:

Write a function isSubsequence which takes in two strings and checks whether the characters in the first string form a subsequence of the characters in the second string. In other words, the function should check whether the characters in the first string appear somewhere in the second string, without their order changing

  1. isSubsequence('hello','hello world') //true
  2. isSubsequence('sing','sting') //true
  3. isSubsequence('abc','abracadabra') //true
  4. isSubsequence('abc', 'acb') //false

This is my code:

const isSubsequence = (str1, str2) => {
  const createCharObj = (string) => {
    let outputObj = {};
    for (let i = 0; i < string.length; i++) {
      if (outputObj[string[i]]) {
        outputObj[string[i]]++;
      } else {
        outputObj[string[i]] = 1;
      }
    }
    return outputObj;
  };
  let charObj1 = createCharObj(str1);
  let charObj2 = createCharObj(str2);
  let compare = "";

  for (let key in charObj2) {
    if (charObj2[key] < charObj1[key]) {
      return false;
    } else {
      let exceed = charObj1[key];
      let i = 0;
      while (i < exceed) {
        compare += key;
        i++;
      }
    }
  }
  return compare === str1;
};

console.log(isSubsequence("hello", "hello world"));
console.log(isSubsequence("sing", "sting"));
console.log(isSubsequence("abc", "abracadabra"));
console.log(isSubsequence("abc", "acb"));

I understand that my solution is not efficient, but I believe that the logic is proper.

However, when I run it on an IDE of Udemy, I get an error saying:

expected false to be true

Yet when I run it on VS code, there was no issue. Please let me know where I did the mistake.

Upvotes: 0

Views: 142

Answers (1)

trincot
trincot

Reputation: 350760

Your algorithm is not correct. The code challenge site (Udemy) is feeding your code with other inputs as well, and for some of those (not the ones you listed) your code returns the wrong result.

It assumes that if a letter in the second string corresponds to a letter in the first string, that it must be the one that is also in the right sequence. This is not necessarily true for the first time this character is encountered in the second string.

For instance, your code will return the wrong result for this input:

console.log(isSubsequence("abc", "acabc"));

This is because in the second string the first occurrence of "c" is before the first occurrence of "b", but it should have ignored that first "c".

Hints:

The main iteration should be over the first string, not the second.

Once a character from the first string is found in the second string, all characters that precede that character in the second string should be completely ignored in any next search.

Spoiler solution:

const isSubsequence = (str1, str2) => { let j = -1; for (let ch of str1) { j = str2.indexOf(ch, j + 1); if (j === -1) return false; } return true; };

Upvotes: 2

Related Questions