SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem requires finding all starting indices of substring(s) in a given string s that is an anagram of a given string p. An anagram of a string is another string that contains the same characters, only the order of the characters can be different.

Intuition

To solve this problem, we need to compare substrings of s with the string p. A substring is an anagram of p if the character frequencies in the substring match the frequencies in p. Therefore, the problem reduces to comparing character frequency counts.

Approach

1. Initialization:

   • Compute the frequency of each character in p and store it in a list pmap.
   • Initialize a list smap to keep track of the frequency of characters in the current window of size equal to p in s.

2. First Window:

   • Populate smap with the frequencies of characters in the first window of length p from s.

3. Sliding Window:

   • Compare smap with pmap. If they are equal, add the starting index of the window to the result list.
   • Slide the window one character at a time to the right by updating smap:
     • Add the frequency of the new character coming into the window.
     • Subtract the frequency of the character leaving the window.

4. Final Check:

   • After the loop, ensure that the last window (if not already checked) is compared with pmap.

5. Return Results:

   • Return the list of starting indices where anagrams are found.

Complexity

Time Complexity:

O(n), where n is the length of the string s. The algorithm processes each character in s once, and the frequency comparison is done in constant time since the frequency arrays have a fixed size (26 for lowercase English letters).

Space Complexity:

O(1). The space used for storing frequency counts is constant (26 elements for each frequency array), and the result list's size depends on the number of valid anagrams found.

Code

C++

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        if (s.length() < p.length()) {
            return result;
        }

        vector<int> pmap(26, 0);
        vector<int> smap(26, 0);

        for (char c : p) {
            pmap[c - 'a']++;
        }

        for (int i = 0; i < p.length(); i++) {
            smap[s[i] - 'a']++;
        }

        if (smap == pmap) {
            result.push_back(0);
        }

        for (int i = p.length(); i < s.length(); i++) {
            smap[s[i] - 'a']++;
            smap[s[i - p.length()] - 'a']--;

            if (smap == pmap) {
                result.push_back(i - p.length() + 1);
            }
        }

        return result;
    }
};

Python

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p):
            return []

        pmap = [0] * 26
        smap = [0] * 26
        result = []

        for char in p:
            pmap[ord(char) - ord('a')] += 1

        for i in range(len(p)):
            smap[ord(s[i]) - ord('a')] += 1

        if smap == pmap:
            result.append(0)

        for i in range(len(p), len(s)):
            smap[ord(s[i]) - ord('a')] += 1
            smap[ord(s[i - len(p)]) - ord('a')] -= 1

            if smap == pmap:
                result.append(i - len(p) + 1)

        return result

Java

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length()) {
            return result;
        }

        int[] pmap = new int[26];
        int[] smap = new int[26];

        for (char c : p.toCharArray()) {
            pmap[c - 'a']++;
        }

        for (int i = 0; i < p.length(); i++) {
            smap[s.charAt(i) - 'a']++;
        }

        if (matches(smap, pmap)) {
            result.add(0);
        }

        for (int i = p.length(); i < s.length(); i++) {
            smap[s.charAt(i) - 'a']++;
            smap[s.charAt(i - p.length()) - 'a']--;

            if (matches(smap, pmap)) {
                result.add(i - p.length() + 1);
            }
        }

        return result;
    }

    private boolean matches(int[] smap, int[] pmap) {
        for (int i = 0; i < smap.length; i++) {
            if (smap[i] != pmap[i]) {
                return false;
            }
        }
        return true;
    }
}

JavaScript

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    if (s.length < p.length) {
        return []
    }
    const pmap = new Array(26).fill(0);
    
    for (let i = 0; i < p.length; i++) {
        pmap[p.charAt(i).charCodeAt(0) - 97]++;
        
    }
    const result = [];
    const smap = new Array(26).fill(0);
    for (let i = 0; i <p.length; i++) {
        smap[s.charAt(i).charCodeAt(0) - 97]++;
    }
    for (let i = 0; i <= s.length - p.length; i++) {
        console.log(smap);
        if (compareArrays(smap, pmap)) {
            result.push(i);
        }
        smap[s.charAt(i).charCodeAt(0)- 97]--;
        smap[s.charAt(i + p.length).charCodeAt(0)- 97]++;
    }
    return result;
};

const compareArrays = (arr1, arr2) => {
    for (let i = 0; i < arr1.length; i++) {
        if (arr1[i] != arr2[i]) {
            return false;
        }
    }

    return true;
}