Strings and 1D Arrays

Given an integer array of length \(N\), rotate the array to the right by \(k\) steps, where \(k \ge 0\).

Rotation is periodical, e.g., rotating a 5-item array 13 times yields the same result as rotating it \( 13 \mod 5 = 3\) times. So our effective \(k\) is \(k \mod N\). That \(k \ge 0\) saves us from worrying about how the programming language implements modulo operations .

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. Return 0 if there is no such subarray.

This reads like an \(^{n}P_{k}\) permutation problem, where we’re trying to minimize \(k\) under the constraint that the sum of elements is greater than target. \(^{n}P_{k}\) can be implemented in a BFS manner, e.g.,

Given two lowercase strings, s and t, return true if s is a subsequence of t, or false otherwise. A subsequence of a string is a string that is formed from the original string by deleting some (can be none) of the characters while maintaining the relative positions of the remaining characters.

My solution was:

public class Solution {
  private string _s;
  private string _t;

  public bool IsSubsequence(string s, string t) {
    _s = s;
    _t = t;
    return IsReachable(0, 0);
  }

  private bool IsReachable(int si, int ti)
  {
    if (si == _s.Length)
      return true;

    char c = _s[si];
    for (int i = ti; i < _t.Length; i++)
    {
      if (_t[i] == c)
        return IsReachable(si + 1, i + 1);
    }
    return false;
  }
}

… where _s and _t avoid unnecessary string copies in the recursion tree.

Minimum Penalty for a Shop. leetcode.com . Accessed Jul 21, 2024.

Problem

You are given the customer visit log of a shop represented by a zero-indexed string customers consisting only of characters N and Y. If the \(i^{th}\) character is Y, it means that customers come at the \(i^{th}\) hour, whereas N indicates that no customers come at the \(i^{th}\) hour.