Anagram coding pattern

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.

242. Valid Anagram

https://leetcode.com/problems/valid-anagram/description/

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

Example 1:

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

Approach

1. We can use array of size 26 to use as hashmap to store the count against each char.
2. For each char in s and t , let’s increment the count for s and decrement the count for t
3. At the end, if it is anagram then all value should be 0 .
4. Otherwise not.

Following is code for reference.

const getIndex = chr => chr.charCodeAt(0) - 'a'.charCodeAt();
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    const m = s.length;
    const n = t.length;
    if(m !== n) {
        return false;
    }
    const count = new Array(26).fill(0);
    for (let i=0; i < m; i++) {
        const x = getIndex(s[i]);
        const y = getIndex(t[i]);
        count[x]++;
        count[y]--;
    }
    for (const value of count ) {
        if(value !== 0) {
            return false;
        }
    }
    return true;
};

49. Group Anagrams

https://leetcode.com/problems/group-anagrams/description/

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Approach 1: Categorize by Sorted String

Create a map to store the anagrams, where the keys are the sorted strings and the values are the lists of anagrams.

Following is code for reference.

const getKey = word => {
    const tokens = word.split('');
    tokens.sort();
    return tokens.join('');
}
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
    const map = new Map();
    for (const word of strs) {
        const key = getKey(word);
        if (!map.has(key)) {
            map.set(key, []);
        }
        map.get(key).push(word);
    }
    return Array.from(map.values());
};

Approach 2: Categorize by count

Two strings are anagrams if and only if their character counts (respective number of occurrences of each character) are the same.

The hashable representation of our count will be a string delimited with ‘#’ characters. For example, abbccc will be #1#2#3#0#0#0...#0 where there are 26 entries total.

const getIndex = chr => chr.charCodeAt(0) - 'a'.charCodeAt(0);
const getKey = word => {
    const freq = new Map();
    for (const chr of word) {
        freq.set(chr, freq.has(chr) ? freq.get(chr) + 1 : 1);
    }
    // Build 26 char length hash
    const key = new Array(26).fill(0);
    for (const [chr, count] of freq) {
        key[getIndex(chr)] = count;
    }
    return key.join('#');
}
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
    const map = new Map();
    for (const word of strs) {
        const key = getKey(word);
        if (!map.has(key)) {
            map.set(key, []);
        }
        map.get(key).push(word);
    }
    return Array.from(map.values());
};

438. Find All Anagrams in a String

https://leetcode.com/problems/find-all-anagrams-in-a-string/description/

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

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 = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Approach

We can use sliding window and keep track of anagram.

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
    const n = s.length;
    const k = p.length;
    const map = new Map();
    for (const chr of p) {
        map.set(chr, map.has(chr) ? map.get(chr) + 1 : 1);
    }
    let total = map.size;
    const ans = [];
    let left = 0;
    for (let right = 0; right < n; right++) {
        const chr = s[right];
        if (map.has(chr)) {
            map.set(chr, map.get(chr) - 1);
            if (map.get(chr) === 0) {
                total--;
            }
        }
        // violation zone
        if (right - left >= k) {
            const chr = s[left];
            if (map.has(chr)) {
                if (map.get(chr) === 0) {
                    total++;
                }
                map.set(chr, map.get(chr) + 1);
            }
            left++;
        }
        // ans zone
        if (total === 0) {
            ans.push(left);
        }
    }
    return ans;
};

1347. Minimum Number of Steps to Make Two Strings Anagram

https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram/description/

You are given two strings of the same length s and t. In one step you can choose any character of t and replace it with another character.

Return the minimum number of steps to make t an anagram of s.

An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.

Example 1:

Input: s = "bab", t = "aba"
Output: 1
Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.

Approach

Find count of chars in t which are not present in s.

/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var minSteps = function (s, t) {
    const count = new Array(26).fill(0);
    const getIndex = chr => chr.charCodeAt(0) - 'a'.charCodeAt(0);
    const n = s.length;
    for (let i = 0; i < n; i++) {
        count[getIndex(t[i])]++;
        count[getIndex(s[i])]--;
    }
    let ans =0;
    // Adding the difference where string int has more instances than s
    // Ignoring where t has fewer instances they are redundant and can be covered by first case
    for (const frequency of count) {
        ans += Math.max(0, frequency);
    }
    return ans;
};

Happy coding :-)