teleren/devto huggingface dataset:
1397. Leetcode Solution in Java
Tags: java
Published: 2022-07-03 17:49:37

```
class Solution {
    public int findGoodStrings(int n, String s1, String s2, String evil) {
        int length = evil.length();
        int[][][] dp = new int[n][length][4];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < length; j++) {
                for (int k = 0; k < 4; k++)
                    dp[i][j][k] = -1;
            }
        }
        int[][] transfers = new int[length][26];
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < 26; j++)
                transfers[i][j] = -1;
        }
        int[] fails = new int[length];
        for (int i = 1; i < length; i++) {
            int state = fails[i - 1];
            while (state > 0 && evil.charAt(state) != evil.charAt(i))
                state = fails[state - 1];
            if (evil.charAt(state) == evil.charAt(i))
                fails[i] = state + 1;
        }
        return depthFirstSearch(n, s1, s2, evil, dp, transfers, fails, 0, 0, 3);
    }

    public int depthFirstSearch(int n, String s1, String s2, String evil, int[][][] dp, int[][] transfers, int[] fails, int index, int state, int bound) {
        final int MODULO = 1000000007;
        int length = evil.length();
        if (state == length)
            return 0;
        if (index == n)
            return 1;
        if (dp[index][state][bound] >= 0)
            return dp[index][state][bound];
        dp[index][state][bound] = 0;
        char low = ((bound & 1) > 0) ? s1.charAt(index) : 'a';
        char high = ((bound & 2) > 0) ? s2.charAt(index) : 'z';
        for (char c = low; c <= high; c++) {
            int nextState = getTransfer(evil, transfers, fails, state, c);
            int nextBound = 0;
            if ((bound & 1) > 0 && c == s1.charAt(index))
                nextBound++;
            if ((bound & 2) > 0 && c == s2.charAt(index))
                nextBound += 2;
            dp[index][state][bound] = (dp[index][state][bound] + depthFirstSearch(n, s1, s2, evil, dp, transfers, fails, index + 1, nextState, nextBound)) % MODULO;
        }
        return dp[index][state][bound];
    }

    public int getTransfer(String evil, int[][] transfers, int[] fails, int state, char letter) {
        int letterIndex = letter - 'a';
        if (transfers[state][letterIndex] >= 0)
            return transfers[state][letterIndex];
        while (state > 0 && evil.charAt(state) != letter)
            state = fails[state - 1];
        int transfer = evil.charAt(state) == letter ? state + 1 : 0;
        transfers[state][letterIndex] = transfer;
        return transfer;
    }
}
```
1402. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-03 17:48:38

```
class Solution {
    typedef long long LL;
public:
    int maxSatisfaction(vector<int>& A) {
        int N = A.size();
        sort(A.begin(), A.end());
        LL ans = 0;
        for (int i = 0; i < N; ++i) {
            LL sum = 0;
            for (int j = i; j < N; ++j) sum += A[j] * (j - i + 1);
            ans = max(ans, sum);
        }
        return ans;
    }
};
```
1411. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-03 17:47:52

```
class Solution {
 public:
  int numOfWays(int n) {
    constexpr int kMod = 1e9 + 7;
    long color2 = 6;  // 121, 131, 212, 232, 313, 323
    long color3 = 6;  // 123, 132, 213, 231, 312, 321

    for (int i = 1; i < n; ++i) {
      const long nextColor2 = color2 * 3 + color3 * 2;
      const long nextColor3 = color2 * 2 + color3 * 2;
      color2 = nextColor2 % kMod;
      color3 = nextColor3 % kMod;
    }

    return (color2 + color3) % kMod;
  }
};

```
1359. Leetcode Soluiton in Cpp
Tags: cpp
Published: 2022-07-03 17:46:30

```
class Solution {
 public:
  int countOrders(int n) {
    constexpr int kMod = 1e9 + 7;
    long ans = 1;

    for (int i = 1; i <= n; ++i)
      ans = ans * i * (i * 2 - 1) % kMod;

    return ans;
  }
};

```
1349. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-03 17:45:10

```
class Solution {
 public:
  int maxStudents(vector<vector<char>>& seats) {
    return accumulate(begin(seats), end(seats), 0,
                      [&](int a, const auto& seat) {
                        return a + count(begin(seat), end(seat), '.');
                      }) -
           hungarian(seats);
  }

 private:
  const vector<pair<int, int>> dirs{{-1, -1}, {0, -1}, {1, -1},
                                    {-1, 1},  {0, 1},  {1, 1}};

  int hungarian(const vector<vector<char>>& seats) {
    const int m = seats.size();
    const int n = seats[0].size();
    int count = 0;
    vector<vector<int>> seen(m, vector<int>(n));
    vector<vector<int>> match(m, vector<int>(n, -1));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (seats[i][j] == '.' && match[i][j] == -1) {
          const int sessionId = i * n + j;
          seen[i][j] = sessionId;
          count += dfs(seats, i, j, sessionId, seen, match);
        }

    return count;
  }

  int dfs(const vector<vector<char>>& seats, int i, int j, int sessionId,
          vector<vector<int>>& seen, vector<vector<int>>& match) {
    const int m = seats.size();
    const int n = seats[0].size();

    for (const auto& [dx, dy] : dirs) {
      const int x = i + dx;
      const int y = j + dy;
      if (x < 0 || x == m || y < 0 || y == n)
        continue;
      if (seats[x][y] != '.' || seen[x][y] == sessionId)
        continue;
      seen[x][y] = sessionId;
      if (match[x][y] == -1 || dfs(seats, match[x][y] / n, match[x][y] % n,
                                   sessionId, seen, match)) {
        match[x][y] = i * n + j;
        match[i][j] = x * n + y;
        return 1;
      }
    }

    return 0;
  }
};

```
1320. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-03 17:44:13

```
class Solution {
    int d(int a, int b) {
        return abs(a / 6 - b / 6) + abs(a % 6 - b % 6);
    }
public:
    int minimumDistance(string word) {
        vector<int> dp(26);
        int res = 0, save = 0, n = word.size();
        for (int i = 0; i < n - 1; ++i) {
            int b = word[i] - 'A', c = word[i + 1] - 'A';
            for (int a = 0; a < 26; ++a)
                dp[b] = max(dp[b], dp[a] + d(b, c) - d(a, c));
            save = max(save, dp[b]);
            res += d(b, c);
        }
        return res - save;
    }
};
```
1289. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-03 17:42:49

```
class Solution {
 public:
  int minFallingPathSum(vector<vector<int>>& grid) {
    const int n = grid.size();

    for (int i = 1; i < n; ++i) {
      const auto twoMinNumAndIndexs = getTwoMinNumAndIndexs(grid[i - 1]);
      const auto& [firstMinNum, firstMinIndex] = twoMinNumAndIndexs[0];
      const auto& [secondMinNum, _] = twoMinNumAndIndexs[1];
      for (int j = 0; j < n; ++j)
        if (j == firstMinIndex)
          grid[i][j] += secondMinNum;
        else
          grid[i][j] += firstMinNum;
    }

    return *min_element(begin(grid.back()), end(grid.back()));
  }

 private:
  vector<pair<int, int>> getTwoMinNumAndIndexs(const vector<int>& A) {
    vector<pair<int, int>> numAndIndexs;

    for (int i = 0; i < A.size(); ++i)
      numAndIndexs.emplace_back(A[i], i);

    sort(begin(numAndIndexs), end(numAndIndexs));
    return {numAndIndexs[0], numAndIndexs[1]};
  }
};

```
1284. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-03 17:42:06

```
// Time: O(MN * 2^(MN))
// Space: O(2^(MN))
class Solution {
public:
    int minFlips(vector<vector<int>>& A) {
        int start = 0, M = A.size(), N = A[0].size(), step = 0, dirs[5] = {1,0,-1,0,1};
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                start |= (A[i][j] << (i * 3 + j));
            }
        }
        queue<int> q;
        unordered_set<int> s;
        q.push(start);
        s.insert(start);
        while (q.size()) {
            int cnt = q.size();
            while (cnt--) {
                int state = q.front();
                q.pop();
                if (state == 0) return step;
                for (int i = 0; i < 9; ++i) {
                    int next = state, r = i / 3, c = i % 3;
                    next ^= (1 << (r * 3 + c));
                    for (int j = 0; j < 4; ++j) {
                        int x = r + dirs[j], y = c + dirs[j + 1];
                        if (x < 0 || x >= M || y < 0 || y >= N) continue;
                        next ^= (1 << (x * 3 + y));
                    }
                    if (s.count(next) == 0) {
                        q.push(next);
                        s.insert(next);
                    }
                }
            }
            ++step;
        }
        return -1;
    }
};
```
1269. Leetcode Solution in CPP
Tags: cpp
Published: 2022-07-03 17:41:27

```
class Solution {
 public:
  int numWays(int steps, int arrLen) {
    constexpr int kMod = 1e9 + 7;
    const int n = min(arrLen, steps / 2 + 1);
    // dp[i] := # of ways to stay on index i
    vector<long> dp(n);
    dp[0] = 1;

    while (steps--) {
      vector<long> newDp(n);
      for (int i = 0; i < n; ++i) {
        newDp[i] = dp[i];
        if (i - 1 >= 0)
          newDp[i] += dp[i - 1];
        if (i + 1 < n)
          newDp[i] += dp[i + 1];
        newDp[i] %= kMod;
      }
      dp = move(newDp);
    }

    return dp[0];
  }
};

```
864. Leetcode solution in Cpp
Tags: cpp
Published: 2022-07-03 16:59:35

```
struct T {
  int i;
  int j;
  int keys;  // keys in bitmask
  T(int i, int j, int keys) : i(i), j(j), keys(keys) {}
};

class Solution {
 public:
  int shortestPathAllKeys(vector<string>& grid) {
    const int m = grid.size();
    const int n = grid[0].length();
    const int keysCount = getKeysCount(grid);
    const int kKeys = (1 << keysCount) - 1;
    const vector<int> dirs{0, 1, 0, -1, 0};
    const vector<int> start = getStart(grid);
    int ans = 0;
    queue<T> q{{{start[0], start[1], 0}}};
    vector<vector<vector<bool>>> seen(
        m, vector<vector<bool>>(n, vector<bool>(kKeys)));
    seen[start[0]][start[1]][0] = true;

    while (!q.empty()) {
      ++ans;
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [i, j, keys] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k) {
          const int x = i + dirs[k];
          const int y = j + dirs[k + 1];
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          const char c = grid[x][y];
          if (c == '#')
            continue;
          const int newKeys = 'a' <= c && c <= 'f' ? keys | 1 << c - 'a' : keys;
          if (newKeys == kKeys)
            return ans;
          if (seen[x][y][newKeys])
            continue;
          if ('A' <= c && c <= 'F' && ((newKeys >> c - 'A') & 1) == 0)
            continue;
          q.emplace(x, y, newKeys);
          seen[x][y][newKeys] = true;
        }
      }
    }

    return -1;
  }

 private:
  int getKeysCount(const vector<string>& grid) {
    int count = 0;
    for (const auto& s : grid)
      count += std::count_if(begin(s), end(s),
                             [](char c) { return 'a' <= c && c <= 'f'; });
    return count;
  }

  vector<int> getStart(const vector<string>& grid) {
    for (int i = 0; i < grid.size(); ++i)
      for (int j = 0; j < grid[0].length(); ++j)
        if (grid[i][j] == '@')
          return {i, j};
    throw;
  }
};

```
1263. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-03 17:40:39

```

// Time: O((MN)^2)
// Space: O((MN)^2)
class Solution {
public:
    int minPushBox(vector<vector<char>>& G) {
        int dp[20][20][20][20] = {}, M = G.size(), N = G[0].size(), sx, sy, bx, by, tx, ty, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }, ans = INT_MAX;
        memset(dp, 0x3f, sizeof(dp));
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (G[i][j] == 'S') sx = i, sy = j;
                else if (G[i][j] == 'B') bx = i, by = j;
                else if (G[i][j] == 'T') tx = i, ty = j;
            }
        }
        queue<vector<int>> q;
        q.push({ sx, sy, bx, by, 0 });
        dp[sx][sy][bx][by] = 0;
        while (q.size()) {
            auto v = q.front();
            q.pop();
            int sx = v[0], sy = v[1], bx = v[2], by = v[3], push = v[4];
            if (bx == tx && by == ty) ans = min(ans, push);
            for (auto [dx, dy] : dirs) {
                int x = sx + dx, y = sy + dy;
                if (x < 0 || y < 0 || x >= M || y >= N || G[x][y] == '#') continue;
                int bx2 = bx, by2 = by, push2 = push;
                if (x == bx && y == by) bx2 += dx, by2 += dy, ++push2;
                if (bx2 < 0 || by2 < 0 || bx2 >= M || by2 >= N || G[bx2][by2] == '#' || push2 >= dp[x][y][bx2][by2]) continue;
                dp[x][y][bx2][by2] = push2;
                q.push({ x, y, bx2, by2, push2 });
            }
        }
        return ans == INT_MAX ? -1 : ans;
    }
};
```
1255. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-03 17:39:26

```
class Solution {
 public:
  int maxScoreWords(vector<string>& words, vector<char>& letters,
                    vector<int>& score) {
    vector<int> count(26);
    for (const char c : letters)
      ++count[c - 'a'];
    return dfs(words, 0, count, score);
  }

 private:
  // max score you can get from words[s:]
  int dfs(const vector<string>& words, int s, vector<int>& count,
          const vector<int>& score) {
    int ans = 0;
    for (int i = s; i < words.size(); ++i) {
      const int earned = useWord(words, i, count, score);
      if (earned > 0)
        ans = max(ans, earned + dfs(words, i + 1, count, score));
      unuseWord(words, i, count);
    }
    return ans;
  }

  int useWord(const vector<string>& words, int i, vector<int>& count,
              const vector<int>& score) {
    bool isValid = true;
    int earned = 0;
    for (const char c : words[i]) {
      if (--count[c - 'a'] < 0)
        isValid = false;
      earned += score[c - 'a'];
    }
    return isValid ? earned : -1;
  }

  void unuseWord(const vector<string>& words, int i, vector<int>& count) {
    for (const char c : words[i])
      ++count[c - 'a'];
  }
};

```
1250. Leetcode Solution in CPP
Tags: cpp
Published: 2022-07-03 17:38:37

```
class Solution {
 public:
  bool isGoodArray(vector<int>& nums) {
    int g = nums[0];

    for (const int num : nums)
      g = __gcd(g, num);

    return g == 1;
  }
};

```
How to remove a specific item from an array
Tags: javascript, webdev, tutorial, beginners
Published: 2022-07-03 17:38:10

One of the most frequent tasks we have to perform in Javascript is to remove a particular item from an array. However, it's not straight forward. There is no `removeArrayItem` method in Javascript, so we have to use alternative methods. Let's look at how to remove a particular array item in Javascript.

## How to remove a specific array item in Javascript

### Option 1: Using filter()
The easiest way with modern Javascript to remove a specific array item is using filter. Let's look at a simple example:
```javascript
let myArr = [ "🍎", "🍏", "🍐", "🍍" ];

// Creates a new array without "🍍" - so [ "🍎", "🍏", "🍐" ]
let removedArr = myArr.filter((x) => x !== "🍍");
console.log(removedArr);
```

This works great when we have an array where every element is **unique**. Unfortunately, it starts to break down if you only want to remove one item, and there are duplicates. Let's look at another example:
```javascript
let myArr = [ "🍎", "🍏", "🍏", "🍍" ];

// Creates a new array without "🍏" - so [ "🍎",  "🍍" ]
let removedArr = myArr.filter((x) => x !== "🍏");
console.log(removedArr);
```

Since we had two green apples, and the new array filters out all green apples, we actually remove two items when using this method. If we only want to remove one element, we have to use an alternative strategy.

## Option 2: Use indexOf() and splice()

This method requires a few more lines, but it is slightly different in a few ways from the previous example:
- First of all, it alters the original array - so we aren't making a copy here. The original array **will** be **mutated**
- Secondly, it uses two functions - first we get the `indexOf` the array item to be removed, and then we `splice` the array to remove that single item.

Here is an example:
```javascript
let myArr = [ "🍎", "🍏", "🍏", "🍍" ];
let getLocation = myArr.indexOf("🍏");
myArr.splice(getLocation, 1);
// myArr now becomes [ "🍎", "🍏",  "🍍" ];
console.log(myArr);
```

This example may be preferable in some situations, but ultimately you'll need to decide what works best in your own code.

## Conclusion
Although there is no straightforward way to remove an item from an array in Javascript, we do have two tools that give us enough flexibility to cover pretty much any use case regarding array item removal. If you want to learn more quick array tips, check out my [array tips guide here](https://fjolt.com/article/javascript-everything-arrays).
1368. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-03 17:37:47

```
class Solution {
public:
    int minCost(vector<vector<int>>& G) {
        int M = G.size(), N = G[0].size(), dp[100][100] = {}, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
        memset(dp, 0x3f, sizeof(dp));
        dp[0][0] = 0;
        queue<pair<int, int>> q;
        q.emplace(0, 0);
        while (q.size()) {
            auto [x, y] = q.front();
            q.pop();
            for (int i = 0; i < 4; ++i) {
                auto &[dx, dy] = dirs[i];
                int a = x + dx, b = y + dy;
                if (a < 0 || b < 0 || a >= M || b >= N) continue;
                if (dp[x][y] + (G[x][y] - 1 != i) < dp[a][b]) {
                    dp[a][b] = dp[x][y] + (G[x][y] - 1 != i);
                    q.emplace(a, b);
                }
            }
        }
        return dp[M - 1][N - 1];
    }
};
```
1363. Leetcode Solution in cpp
Tags: cpp
Published: 2022-07-03 17:37:07

```
class Solution {
public:
    string largestMultipleOfThree(vector<int>& A) {
        int cnt[10] = {}, total = 0;
        for (int n : A) {
            cnt[n]++;
            total += n;
        }
        auto f = [&](int i) {
            if (cnt[i]) {
                cnt[i]--;
                total -= i;
            }
            return total % 3 == 0;
        };
        bool done = total % 3 == 0;
        if (!done) {
            if (total % 3 == 1) done = f(1) || f(4) || f(7) || f(2) || f(2) || f(5) || f(5) || f(8) || f(8);
            else done = f(2) || f(5) || f(8) || f(1) || f(1) || f(4) || f(4) || f(7) || f(7);
        }
        if (!done) cnt[1] = cnt[2] = cnt[4] = cnt[5] = cnt[7] = cnt[8] = 0;
        string ans;
        for (int i = 9; i >= 0; --i) {
            while (cnt[i]-- > 0) ans += '0' + i;
        }
        return ans[0] == '0' ? "0" : ans;
    }
};
```
1125. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-03 17:35:22

```
class Solution {
 public:
  vector<int> smallestSufficientTeam(vector<string>& req_skills,
                                     vector<vector<string>>& people) {
    const int n = req_skills.size();
    const int nSkills = 1 << n;
    unordered_map<string, int> skillToId;
    // dp[i] := min people's indices to cover skillset of mask i
    unordered_map<int, vector<int>> dp;
    dp.reserve(nSkills);  // avoid rehash
    dp[0] = {};

    for (int i = 0; i < n; ++i)
      skillToId[req_skills[i]] = i;

    auto getSkill = [&](const vector<string>& person) {
      int mask = 0;
      for (const string& skill : person)
        if (skillToId.count(skill))
          mask |= 1 << skillToId[skill];
      return mask;
    };

    for (int i = 0; i < people.size(); ++i) {
      const int currSkill = getSkill(people[i]);
      for (const auto& [mask, indices] : dp) {
        const int newSkillSet = mask | currSkill;
        if (newSkillSet == mask)  // adding people[i] doesn't increase skill set
          continue;
        if (!dp.count(newSkillSet) ||
            dp[newSkillSet].size() > indices.size() + 1) {
          dp[newSkillSet] = indices;
          dp[newSkillSet].push_back(i);
        }
      }
    }

    return dp[nSkills - 1];
  }
};

```
1106. Leetcode Solution in Cpp
Tags: cpp
Published: 2022-07-03 17:34:27

```
class Solution {
 public:
  bool parseBoolExpr(string expression) {
    int i = 0;
    return parse(expression, i);
  }

 private:
  bool parse(const string& exp, int& i) {
    if (exp[i] == 't') {
      ++i;
      return true;
    }
    if (exp[i] == 'f') {
      ++i;
      return false;
    }
    if (exp[i] == '!') {
      i += 2;
      bool ans = !parse(exp, i);
      ++i;
      return ans;
    }

    bool isAnd = exp[i] == '&';
    bool ans = isAnd;
    i += 2;
    while (exp[i] != ')') {
      bool parsed = parse(exp, i);
      if (isAnd)
        ans &= parsed;
      else
        ans |= parsed;
      if (exp[i] == ',')
        ++i;
    }
    ++i;
    return ans;
  }
};

```
JavaScript Interview Coding Test Problem 2
Published: 2022-07-02 14:30:56

**Maximum Profits**
We'll discuss how to write a function that can reap the maximum profits from a day's stock data. We'll discuss both the simple brute-force solution and an elegant solution to this problem.

**Instructions**
Suppose we could access yesterday’s prices for a certain stock as a chronological list. Write a function that takes the list and returns the highest profit possible from one purchase and one sale of the stock yesterday.
For example, a stock price list of [18, 7, 5, 8, 11, 9] Shows that the stock started at i8 and ended at , going through the numbers chronologically. There is at least a 1-minute difference between the stock prices.
Taking that array as input, our function should return 6, the maximum possible profit from buying when the price was s and selling when the price was ii.
If no profit can be made, return 8.

No “shorting” — you must buy befDre you sell. You may not buy and sell in the same time step.
Input: Array of Numbers
Output: Number

**Hints**
  • We’ll have to convert this array of stock prices into possible profits
  • Think about the fact that this is a chronologically ordered list.
  
```
function getMaxProfit(prices) {
    // Your code here 3
  }
```

**Solution**
let count = 0; 2
function getMaxProfit(prices) {
  const possibleProfits = [];

  for(let i = 0; i < prices.length; i++) (
    for(let j = i; j < prices.length; j++) {
      possibleProfits.push(prices[j] - prices[i]);
      count++;
      return Math.max(...possibleProfits);
    }

  getMaxProfit([1, 2, 3]);
  console.log(count);
}

**The Loop**
The second line in the loop updates our minimum price if necessary.
The third line updates the maximum profit if the profit from buying at our current minimum price and selling at the current number is greater than the current max profit.
At the end, we return that maximum profit.

**Time**
This time, we go through the array only once, giving us an efficiency of:
**0(n)**
Much better than o(n^2) 

**Space**
We don’t create any arrays or store values across lDop iteratiDns. All we track is the two variables declared at the beginning. We maintain the same amount of information regardless of array size, so we have a space complexity of
**0(1)**
It’s the best we can get.
**Conclusion**
This is the solution that would win the interviewer over. It’s difficult and it shows the ability to logically deal with hoth numbers and time. It’s elegant, short and sweet. It has the best time and space complexities imaginable for this type of problem.
Take away the idea that there are times when you can turn an o(n^2) solution into an O(n) solution with some critical thinking. Occasionally, keeping track of important values and updating them in the loop will vastly speed up a function.