Skip to content

2744. Find Maximum Number of String Pairs 👍

  • Time: $O(n)$
  • Space: $O(26^2) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int maximumNumberOfStringPairs(vector<string>& words) {
    int ans = 0;
    vector<bool> seen(26 * 26);

    for (const string& word : words) {
      if (seen[val(word[1]) * 26 + val(word[0])])
        ++ans;
      seen[val(word[0]) * 26 + val(word[1])] = true;
    }

    return ans;
  }

 private:
  constexpr int val(char c) {
    return c - 'a';
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int maximumNumberOfStringPairs(String[] words) {
    int ans = 0;
    boolean[] seen = new boolean[26 * 26];

    for (final String word : words) {
      if (seen[val(word.charAt(1)) * 26 + val(word.charAt(0))])
        ++ans;
      seen[val(word.charAt(0)) * 26 + val(word.charAt(1))] = true;
    }

    return ans;
  }

  private final int val(char c) {
    return c - 'a';
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def maximumNumberOfStringPairs(self, words: list[str]) -> int:
    ans = 0
    seen = [False] * (26 * 26)

    def val(c: str) -> int:
      return string.ascii_lowercase.index(c)

    for word in words:
      if seen[val(word[1]) * 26 + val(word[0])]:
        ans += 1
      seen[val(word[0]) * 26 + val(word[1])] = True

    return ans