leetcode-javascript/solutions/0727-minimum-window-subsequence.js at development · Anuj9826/leetcode-javascript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
 * Minimum Window Subsequence
 * Time Complexity: O(S1 * S2)
 * Space Complexity: O(S1 * S2)
 */
var minWindow = function (s1, s2) {
  const primaryStringLength = s1.length;
  const secondaryStringLength = s2.length;

  const dynamicProgramTable = Array.from(
    { length: secondaryStringLength + 1 },
    () => Array(primaryStringLength + 1).fill(Infinity),
  );

  for (
    let stringOneIter = 0;
    stringOneIter <= primaryStringLength;
    stringOneIter++
  ) {
    dynamicProgramTable[0][stringOneIter] = 0;
  }

  for (
    let currentS1Position = 1;
    currentS1Position <= primaryStringLength;
    currentS1Position++
  ) {
    for (
      let currentS2Position = 1;
      currentS2Position <= secondaryStringLength;
      currentS2Position++
    ) {
      if (s1[currentS1Position - 1] === s2[currentS2Position - 1]) {
        dynamicProgramTable[currentS2Position][currentS1Position] =
          dynamicProgramTable[currentS2Position - 1][currentS1Position - 1] + 1;
      } else {
        if (
          dynamicProgramTable[currentS2Position][currentS1Position - 1] !==
          Infinity
        ) {
          dynamicProgramTable[currentS2Position][currentS1Position] =
            dynamicProgramTable[currentS2Position][currentS1Position - 1] + 1;
        }
      }
    }
  }

  let overallMinimumLength = Infinity;
  let windowEndLocation = -1;

  for (
    let scanFinalPosition = 1;
    scanFinalPosition <= primaryStringLength;
    scanFinalPosition++
  ) {
    if (
      dynamicProgramTable[secondaryStringLength][scanFinalPosition] <
      overallMinimumLength
    ) {
      overallMinimumLength =
        dynamicProgramTable[secondaryStringLength][scanFinalPosition];
      windowEndLocation = scanFinalPosition;
    }
  }

  if (overallMinimumLength === Infinity) {
    return "";
  } else {
    const windowStartLocation = windowEndLocation - overallMinimumLength;
    return s1.substring(windowStartLocation, windowEndLocation);
  }
};