Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Function that use Sliding Window isn`t working

The function should return the length of the maximum substring in which there are no duplicate characters, but the program runs for an infinite amount of time

function findMaxLength(str) {
  let right = 0;
  let left = 0;
  let answer = 0;
  let arr = [];

  while (right < str.length) {
    let ch = str.split("")[right];
    if (!arr.includes(ch)) {
      arr.push(ch);
      answer = Math.max(answer, (right - left + 1));
      right++;
    } else {
      while (arr.includes(ch)) {
        arr.splice(left, 1);
        left++;
      }
    }
  }

  return answer;
}
Tags:

2

Answers


  1. 0

    The issue is the use of arr.includes(ch) inside the while loop. You are removing elements from arr using arr.splice(left, 1) inside the loop, therefore the condition arr.includes(ch) might not evaluate correctly.

    function findMaxLength(str) {
  let right = 0;
  let left = 0;
  let answer = 0;
  let arr = new Set();

  while (right < str.length) {
    let ch = str.charAt(right);
    if (!arr.has(ch)) {
      arr.add(ch);
      answer = Math.max(answer, right - left + 1);
      right++;
    } else {
      arr.delete(str.charAt(left));
      left++;
    }
  }

  return answer;
}

console.log(findMaxLength("abaadfa"));
console.log(findMaxLength("qoeurqoiwukajsdflj"));
console.log(findMaxLength("uuuuaaauuu"));
    Login or Signup to reply.
  2. 0

    As an alternative, are you familiar with the lcs algorithm? It might suit your use case if we modify it slightly:

    function lcs(a, b) {
    const m = a.length + 1;
    const n = b.length + 1;

    const weights = new Array(m).fill(0).map(() => new Array(n).fill(0));
    const paths = new Array(m - 1).fill(0).map(() => new Array().fill(""));

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (a[i - 1] == b[j - 1]) {
                weights[i][j] = weights[i - 1][j - 1] + 1;
                paths[i - 1][j - 1] = "u2196";
            } else if (weights[i - 1][j] >= weights[i][j - 1]) {
                weights[i][j] = weights[i - 1][j];
                paths[i - 1][j - 1] = "u2191";
            } else {
                weights[i][j] = weights[i][j - 1];
                paths[i - 1][j - 1] = "u2190";
            }
        }
    }

    return { weights, paths };
}

const args = document.querySelectorAll(".arg");

// The below is a demonstration. Adapt it as needed.
for (let arg of args) {
    const text = arg.firstElementChild.innerText;
    const maxs = [1]; // egde case for strings with length 1

    for (let i = 0; i < text.length - 1; i++) {
        const seen = [text[i]];

        for (let j = i + 1; j < text.length; j++) {
            if (seen.includes(text[j])) {
                break;
            }

            const res = lcs(text, text.slice(i, j))["weights"];
            maxs.push(res[res.length - 1][res[0].length - 1]);
            seen.push(text[j]);
        }
    }

    maxs.sort((a, b) => a - b);

    const elm = document.createElement("div");
    elm.appendChild(document.createTextNode(`${maxs[maxs.length - 1]}`));
    arg.appendChild(elm);
}
    body {
  font-family: Arial, sans-serif;
}

.arg {
  display: flex;
  flex-flow: row nowrap;
  gap: 10px;
}
    <div class="arg">
  <div>
    foobar
  </div>
</div>

<div class="arg">
  <div>
    foofoo
  </div>
</div>

<div class="arg">
  <div>
    abcdefghfooabc
 </div>
</div>

<div class="arg">
  <div>
    fooabcfoo
 </div>
</div>

    Note that the paths array in the algorithm isn’t needed for your use case, I simply lifted the code from here

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search