September LeetCoding Challenge, Day 7: Word Pattern

September 8, 2020

This is part of a series of posts about the September LeetCoding Challenge. Check the first post for more information.

The problem for September 7 is Word Pattern. You’re given two strings. One of them consists of lowercase letters and the other consists of lowercase letters separated by spaces. You want to find out if a bijection exists between the characters of the first string and the words in the second string. In other words, you want to return true if there is a one-to-one correspondence between the characters of the first string and the characters of the second string, and false otherwise.

If the number of words is different from the number of characters, then you can be sure that no bijection exists. If the number of words is the same, we can go word by word and check if a word happens to be mapped to different characters. If it does, then no bijection exists. This is still not sufficient to determine a bijection, since the same character can still be mapped to different words. In order for a bijection to exist, the number of different words must be equal to the number of different characters. Combining all those checks lets us determine if there is a one-to-one correspondence between characters and words. The following is an implementation of the previous idea:

class Solution {
private:
  vector<string> split(string str) {
    istringstream ss(str);
    vector<string> ans;
    string curr;
    while (ss >> curr)
      ans.push_back(curr);
    return ans;
  }

public:
  bool wordPattern(string pattern, string str) {
    vector<string> words = split(str);
    if (words.size() != pattern.size())
      return false;
    unordered_map<string, char> pat;
    set<char> used;
    int N = words.size();
    for (int i = 0; i < N; ++i) {
      if (pat.find(words[i]) != pat.end() && pat[words[i]] != pattern[i])
        return false;
      pat[words[i]] = pattern[i];
      used.insert(pattern[i]);
    }
    return pat.size() == used.size();
  }
};

September LeetCoding Challenge, Day 6: Image Overlap

September 8, 2020

This is part of a series of posts about the September LeetCoding Challenge. Check the first post for more information.

The problem for September 6 is Image Overlap. You’re given two images represented as binary, square matrices, of the same size. You want to translate one of the images by sliding it left, right, up or down any number of units such that, when placed on top of the other image, the number of 1s that overlap in both images is maximized. The length of the side of the images is at most 30.

The length of the side of the images is small enough for us to try all possible translations in \(\mathcal{O}(n^4)\). The following is an implementation of that strategy:

class Solution {
public:
  int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
    int L = A.size(), ans = 0;
    for (int di = -L + 1; di < L; ++di) {
      for (int dj = -L + 1; dj < L; ++dj) {
        int curr = 0;
        for (int i = 0; i < L; ++i) {
          for (int j = 0; j < L; ++j) {
            int bi = i + di, bj = j + dj, vb = 0;
            if (bi >= 0 && bi < L && bj >= 0 && bj < L)
              vb = B[bi][bj];
            if (A[i][j] == 1 && vb == 1)
              curr++;
          }
        }
        ans = max(ans, curr);
      }
    }
    return ans;
  }
};

September LeetCoding Challenge, Day 5: All Elements in Two Binary Search Trees

September 6, 2020

This is part of a series of posts about the September LeetCoding Challenge. Check the first post for more information.

The problem for September 5 is All Elements in Two Binary Search Trees. We’re interested in, given two binary search trees of integers, returning a sorted list of all the integers from both trees.

Since we’re dealing with binary search trees here, each node is guaranteed to store a key greater than all the keys in the node’s left subtree and less than those in its right subtree. As such, an in-order traversal of the tree is guaranteed to produce a sorted list of its elements. We can do an in-order traversal of a binary tree with \(n\) nodes in \(\mathcal{O}(n)\). Having two sorted lists of size \(a\) and \(b\), we can merge them in a new sorted list in \(\mathcal{O}(a + b)\). With these two building blocks, we can produce an algorithm to return the sorted list of all integers of both trees in \(\mathcal{O}(n + m)\), \(n\) being the number of nodes in the first tree, and \(m\) being the number of nodes in the second tree. The following is an implementation of that idea:

class Solution {
private:
  void in_order_traverse(TreeNode* curr, vector<int>& list) {
    if (curr != nullptr) {
      in_order_traverse(curr->left, list);
      list.push_back(curr->val);
      in_order_traverse(curr->right, list);
    }
  }

public:
  vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
    vector<int> list1, list2;
    in_order_traverse(root1, list1);
    in_order_traverse(root2, list2);
    vector<int> ans;
    int N1 = list1.size(), N2 = list2.size(), i1 = 0, i2 = 0;
    while (i1 < N1 || i2 < N2) {
      if (i1 >= N1)
        ans.push_back(list2[i2++]);
      else if (i2 >= N2)
        ans.push_back(list1[i1++]);
      else if (list1[i1] < list2[i2])
        ans.push_back(list1[i1++]);
      else
        ans.push_back(list2[i2++]);
    }
    return ans;
  }
};

September LeetCoding Challenge, Day 4: Partition Labels

September 5, 2020

This is part of a series of posts about the September LeetCoding Challenge. Check the first post for more information.

The problem for September 4 is Partition Labels. According to the problem statement, we have a string \(S\) of lowercase English characters which we want to partition in as many parts as possible. The catch is that each letter must appear in at most one part. Each part is a substring, not a subsequence of string \(S\). For example, given string \(S\) equal to "ababcbacadefegdehijhklij", the valid partition that produces most parts is "ababcbaca", "defegde" and "hijhklij".

Once we select a given character to belong to a part, then all characters with the same letter as the chosen character must belong to that part. In sum, each part must go as far as the last occurrence of each letter in the part. We can solve this in \(\mathcal{O}(|S|)\) by first identifying the indices of the last occurrences of each letter, and then greedily collect characters for each part until the previous restriction is satisfied. The following is an implementation of that strategy:

class Solution {
public:
  vector<int> partitionLabels(string S) {
    vector<int> ans;
    unordered_map<char, int> last;
    int N = S.size();
    for (int i = 0; i < N; ++i)
      last[S[i]] = i;
    int curr = 0;
    int prev = -1;
    for (int i = 0; i < N; ++i) {
      curr = max(curr, last[S[i]]);
      if (curr == i) {
        ans.push_back(curr - prev);
        prev = curr;
      }
    }
    return ans;
  }
};

September LeetCoding Challenge, Day 3: Repeated Substring Pattern

September 4, 2020

This is part of a series of posts about the September LeetCoding Challenge. Check the first post for more information.

The problem for September 3 is Repeated Substring Pattern. The problem statement is straightforward: given an non-empty string of at most 10000 characters, check if it can be constructed by taking a substring of it and appending multiple (more than one) copies of it. In other words, the function should return true if, for a given string \(s\), there exists a proper substring \(m\) of \(s\) such that \(s = m + \dots + m = n \times m\), for \(n > 1\).

The size of the string is small enough to check all proper substrings of \(s\) (in \(\mathcal{O}(n^2)\) time). The following is an implementation of that strategy:

class Solution {
private:
  bool is_rep(const string& rep, const string& s) {
    int R = rep.size(), S = s.size(), ir = 0;
    if (R == S || S % R != 0)
      return false;
    for (int i = 0; i < S; ++i) {
      if (s[i] != rep[ir])
        return false;
      ir = (ir + 1) % R;
    }
    return ir == 0;
  }

public:
  bool repeatedSubstringPattern(string s) {
    string rep = "";
    for (char ch : s) {
      rep += ch;
      if (is_rep(rep, s))
        return true;
    }
    return false;
  }
};

The previous solution is good enough, but some improvements can still be performed under the same strategy. Namely, it’s not necessary to check for substrings larger than half the size of \(s\), and there’s no need to build a new string for the prefix (we can just keep track of the size of the substring under consideration). However, those improvements don’t improve the asymptotic time complexity of the solution.

One key observation for a solution with a better asymptotic time complexity is that if we have a string \(s\) of size \(N\) composed of \(n\) repetitions of substring \(m\) (let’s say that \(s = n \times m\)), and we append string \(s\) onto itself (i.e. we have \(s + s = 2 \times n \times m\)), then \(s\) can also be found in \(s + s\) starting in an index other than \(0\) or \(N\) (since \(|s + s| = 2N\)). Building on this insight, we can append \(s\) onto itself, remove the first and last character of it and try to find an occurrence of \(s\) in the resulting string. If we find it, then \(s\) must be built using a repeated substring pattern. We remove the first and last character to avoid finding the instances of \(s\) starting at index \(0\) and index \(N\). If we’re able to find \(s\) in the resulting string in \(\mathcal{O}(N)\), then we arrive at an \(\mathcal{O}(N)\) solution for this problem. The Knuth-Morris-Pratt (KMP) algorithm allows searching for occurrences of a word \(W\) within a main text string \(S\) in \(\mathcal{O}(|W|) + \mathcal{O}(|S|)\) using \(\mathcal{O}(|W|)\) extra space, and is therefore suitable for our use case. I won’t go into details describing the KMP algorithm. The following is an implementation of the previously described strategy:

class Solution {
private:
  bool kmp(const string& W, const string& S) {
    int M = W.size(), N = S.size();
    vector<int> T(M, 0);
    int len = 0;
    T[0] = 0;
    int i = 1;
    while (i < M) {
      if (W[i] == W[len]) {
        len++;
        T[i] = len;
        i++;
      } else if (len != 0) {
        len = T[len - 1];
      } else {
        T[i] = 0;
        i++;
      }
    }
    int j;
    i = j = 0;
    while (i < N) {
      if (W[j] == S[i]) {
        j++;
        i++;
      }
      if (j == M)
        return true;
      if (W[j] != S[i]) {
        if (j != 0)
          j = T[j - 1];
        else
          i = i + 1;
      }
    }
    return false;
  }

public:
  bool repeatedSubstringPattern(string s) {
    string res = (s + s).substr(1, s.size() * 2 - 2);
    return kmp(s, res);
  }
};