thảo luận Leetcode mỗi ngày

function checkInclusion(s1: string, s2: string): boolean {
  const s1Length = s1.length
  const s2Length = s2.length
  if (s1Length > s2Length) return false;
  const s1Sorted = s1.split('').sort().join('');
  let result = false
  for (let i = 0; (i + s1Length) <= s2Length; i++ ) {
    let s2Sorted = s2.slice(i, i + s1Length).split('').sort().join('')
    if (s1Sorted === s2Sorted) {
      result = true
      break
    }
  }
  return result
}

function checkInclusion(s1: string, s2: string): boolean {
  const s1Length = s1.length
  const s2Length = s2.length
  if (s1Length > s2Length) return false;
  if (s1 === s2) return true;
  const aCode = 'a'.charCodeAt(0)
  const s1CharFrequenci = Array(26).fill(0)
  const s2CharFrequenci = Array(26).fill(0)
  let result = false
  for (let i = 0; i < s1Length; i++) {
    s1CharFrequenci[s1.charCodeAt(i) - aCode]++
    s2CharFrequenci[s2.charCodeAt(i) - aCode]++
  }
  for (let i = s1Length; i <= s2Length; i++) {
    if (s1CharFrequenci.every((element, index) => element === s2CharFrequenci[index])) {
      result = true
      break
    }
    s2CharFrequenci[s2.charCodeAt(i) - aCode]++
    s2CharFrequenci[s2.charCodeAt(i - s1Length) - aCode]-- 
  } 
  return result
}

fun checkInclusion(s1: String, s2: String): Boolean {
    var left = 0
    var right = 0
    val originFreqArr = IntArray(26) { -1 }
    for (c in s1) {
        if (originFreqArr[c - 'a'] < 0) {
            originFreqArr[c - 'a'] = 1
        } else {
            originFreqArr[c - 'a']++
        }
    }
    var freqArr = originFreqArr.clone()
    while (right < s2.length) {
        if (freqArr[s2[right] - 'a'] >= 0) {
            if (freqArr[s2[right] - 'a'] == 0) {
                while (left < right && freqArr[s2[right] - 'a'] == 0) {
                    freqArr[s2[left] - 'a']++
                    left++
                }
            }
            freqArr[s2[right] - 'a']--
            right++
            if (right - left == s1.length) return true
       } else {
            right++
            left = right
            freqArr = originFreqArr.clone()
        }
    }
    return false
}

function isAnAnagram(f1: number[], f2:number[]): boolean {
  let result = true
  const f1Length = f1.length
  for (let i = 0; i < f1Length; i++) {
    if (f1[i] !== f2[i]) {
      result = false
      break
    }
  }

  return result
}

function findAnagrams(s: string, p: string): number[] {
  let result = []
  const sLength = s.length
  const pLength = p.length
  if (sLength < pLength) return result
  const aCode = 'a'.charCodeAt(0)
  const sFrequenci = Array(26).fill(0)
  const pFrequenci = Array(26).fill(0)
  for (let i = 0; i < pLength; i++) {
    pFrequenci[p.charCodeAt(i) - aCode]++
    sFrequenci[s.charCodeAt(i) - aCode]++
  }
  if (sLength === pLength && isAnAnagram(pFrequenci, sFrequenci)) {
    return [0]
  }
  for (let i = pLength; i <= sLength; i++) {
    if (isAnAnagram(pFrequenci, sFrequenci)) {
      result.push(i - pLength)
    }
    sFrequenci[s.charCodeAt(i) - aCode]++
    sFrequenci[s.charCodeAt(i - pLength) - aCode]--
  }
  return result
};

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (p.length() > s.length()) return new ArrayList<>();
        int[] map1 = new int[26];
        int[] map2 = new int[26];

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

        List<Integer> ans = new ArrayList<>();
        int left = 0, right = 0;
        while (right < s.length()) {
            if (right - left + 1 > p.length()) {
                map2[s.charAt(left) - 'a']--;
                left++;
            }
            map2[s.charAt(right) - 'a']++;
            if (isEqual(map1, map2)) ans.add(left);
            right++;
        }
        return ans;
    }

    public boolean isEqual(int[] map1, int[] map2) {
        for (int i = 0; i <= 25; i++) {
            if (map1[i] != map2[i]) return false;
        }

        return true;
    }
}

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    const m = p.length, n = s.length;

    if (m > n) {
        return [];
    }

    const g = Array(26).fill(0);
    for (const ch of p) {
        g[ch.charCodeAt(0) - 97]++;
    }

    let j = 0, ans = [];
    for (let i = 0; i < n; i++) {
        const charIdx = s.charCodeAt(i) - 97;
        g[charIdx]--;

        while (g[charIdx] < 0) {
            g[s.charCodeAt(j++) - 97]++;
        }

        if (i - j + 1 === m) {
            ans.push(j);
        }
    }

    return ans;
};

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if (len(p) > len(s)):
            return []
        result = []
        freq = create_freq_array(p)
        current_freq = {}
        for start in range(0, len(s) - len(p) + 1):
            if start == 0:
                for index in range(start, len(p)):
                    push_dict(current_freq, s[index])
            else:
                push_dict(current_freq, s[start + len(p) - 1])

            flag = True
            for key in current_freq:
                if freq[ord(key) - 97] != current_freq[key]:
                    flag = False
                    break

            if flag:
                result.append(start)

            current_freq[s[start]] -= 1

        return result

def create_freq_array(s: str):
    freq = [0 for i in range(26)]
    for c in s:
        freq[ord(c) - 97] += 1

    return freq

def push_dict(dict: {}, c: str):
    if c in dict:
        dict[c] += 1
    else:
        dict[c] = 1

fun findAnagrams(s: String, p: String): List<Int> {
        val result = mutableListOf<Int>()
        var left = 0
        var right = 0
        val originFreqArr = IntArray(26) { -1 }
        for (c in p) {
            if (originFreqArr[c - 'a'] < 0) {
                originFreqArr[c - 'a'] = 1
            } else {
                originFreqArr[c - 'a']++
            }
        }
        var freqArr = originFreqArr.clone()
        while (right < s.length) {
            if (freqArr[s[right] - 'a'] >= 0) {
                if (freqArr[s[right] - 'a'] == 0) {
                    while (left < right && freqArr[s[right] - 'a'] == 0) {
                        freqArr[s[left] - 'a']++
                        left++
                    }
                }
                freqArr[s[right] - 'a']--
                right++
                if (right - left == p.length) {
                    result.add(left)
                    freqArr[s[left] - 'a']++
                    left++
                }
            } else {
                right++
                left = right
                freqArr = originFreqArr.clone()
            }
        }
        return result
    }

function shuffle(nums: number[], n: number): number[] {
    if (nums.length === 2) {
        return nums;
    }
    let arr: number[] = [];
    for (let i = 0; i < n; i++) {
        arr.push(nums[i]);
        arr.push(nums[i+n]);
    }
    return arr;
};

function shuffle(nums: number[], n: number): number[] {
  const result = []
  for (let i = 0; i < n; i++) {
    result.push(nums[i], nums[n+i])
  }
  return result
};