Valid Anagram

Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Constraints:

  • 1 <= s.length, t.length <= 5 * 10^4
  • s and t consist of lowercase English letters.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Solution

This will have a similar solution to First Unique.

We can count the characters in each and see if they are equal.

For the follow up question, we could swap the arrays with a Map<Character, Integer>. We’d iterate over the contents of both strings and calculate how many times each Unicode character is used.

We’d then iterate over the contents of both maps and ensure they are equal. This would be O(1) insertion, O(1) lookup with a HashMap, meaning the algorithm overall would still be O(n) time, though the space would increase from O(1) to O(n).

class Solution {
    public boolean isAnagram(String s, String t) {
        var l = new int[26];
        var r = new int[26];

        for (var c : s.toCharArray()) {
            l[((int) c) - 97] += 1;
        }

        for (var c : t.toCharArray()) {
            r[((int) c) - 97] += 1;
        }

        for (int i = 0; i < 26; i++) {
            if (l[i] == r[i]) {
                continue;
            }
            return false;
        }

        return true;
    }
}

Recent posts from blogs that I like

An Introduction to Google’s Approach to AI Agent Security

via Simon Willison

Notes on Cramer's rule

Cramer's rule is a clever solution to the classical system of linear equations Ax=b: \[\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix} \begin{bmatrix}x_1 \\ x_2 \\ x_3\end{bmatrix} = \begin{bmatrix}b_1 \\ b_2 \\ b_3\end{bmatrix}\] Usi...

via Eli Bendersky

Brandjes: Paintings as witnesses to fires 1640-1813

Dramatic paintings of towns and cities on fire, usually at night, were popular during the Dutch Golden Age, and known as brandjes. Examples to well into the 19th century.

via The Eclectic Light Company