is sebset

is-subset.ts

// Write a function that takes two arrays as input, each array contains a list of A-Z;
// Your program should return True if the 2nd array is a subset of 1st array, or False if not.

// For example:
// isSubset([A,B,C,D,E], [A,E,D]) = true
// isSubset([A,B,C,D,E], [A,D,Z]) = false
// isSubset([A,D,E], [A,A,D,E]) = true

import { test, expect } from "vitest";

function isSubset(arr1: string[], arr2: string[]) {
  arr1 = arr1.sort();
  arr2 = arr2.sort();

  let p1 = 0;
  let p2 = 0;

  while (p1 < arr1.length && p2 < arr2.length) {
    if (arr1[p1] !== arr2[p2]) {
      p1 += 1;
      continue;
    }

    // arr1[p1] === arr2[p2]
    p1 += 1;
    p2 += 1;

    // move to next distinct character
    while (arr1[p1] === arr1[p1 - 1]) p1 += 1;
    while (arr2[p2] === arr2[p2 - 1]) p2 += 1;
  }

  return p1 === arr1.length && p2 === arr2.length;
}

test("isSubset([A,B,C,D,E], [A,E,D]) = true", () => {
  expect(isSubset(["A", "B", "C", "D", "E"], ["A", "E", "D"])).toBe(true);
});

test("isSubset([A,B,C,D,E], [A,D,Z]) = false", () => {
  expect(isSubset(["A", "B", "C", "D", "E"], ["A", "D", "Z"])).toBe(false);
});

test("isSubset([A,D,E], [A,A,D,E]) = true", () => {
  expect(isSubset(["A", "D", "E"], ["A", "A", "D", "E"])).toBe(true);
});