Weekly Contest 484

Contest Information

Field Value
Date January 11, 2026
Time 09:30 UTC
Duration 90 minutes
Contest Link LeetCode

Problems

Q1. Count Residue Prefixes

Field Value
Difficulty Easy
Points 3
Link LeetCode

Problem Description

You are given a string s consisting only of lowercase English letters.

A prefix of s is called a residue if the number of distinct characters in the prefix is equal to len(prefix) % 3.

Return the count of residue prefixes in s.

Example 1:

Input: s = “abc”

Output: 2

Explanation:

  • Prefix "a" has 1 distinct character and length modulo 3 is 1, so it is a residue.
  • Prefix "ab" has 2 distinct characters and length modulo 3 is 2, so it is a residue.
  • Prefix "abc" does not satisfy the condition. Thus, the answer is 2.

Constraints:

  • 1 <= s.length <= 100
  • s contains only lowercase English letters.
💡 Hints & Approach

Key Insight: For each prefix, track distinct characters and compare with length % 3.

Hint 1: Use a set to track distinct characters as you build each prefix.

Hint 2: Check the condition: distinct_count == prefix_length % 3.

Hint 3: Note that max distinct can be 26, while length % 3 can only be 0, 1, or 2.

Approach:

  1. Iterate through each prefix (length 1 to n)
  2. Track distinct characters using a set
  3. Count prefixes where len(distinct) == prefix_len % 3
def countResiduePrefixes(s):
  distinct = set()
  count = 0
  for i, char in enumerate(s):
    distinct.add(char)
    prefix_len = i + 1
    if len(distinct) == prefix_len % 3:
      count += 1
  return count

Time Complexity: O(n) Space Complexity: O(26) = O(1)

Q2. Number of Centered Subarrays

Field Value
Difficulty Medium
Points 4
Link LeetCode

Problem Description

You are given an integer array nums.

A subarray of nums is called centered if the sum of its elements is equal to at least one element within that same subarray.

Return the number of centered subarrays of nums.

Example 1:

Input: nums = [-1,1,0]

Output: 5

Explanation:

  • All single-element subarrays ([-1], [1], [0]) are centered.
  • The subarray [1, 0] has a sum of 1, which is present in the subarray.
  • The subarray [-1, 1, 0] has a sum of 0, which is present in the subarray.
  • Thus, the answer is 5.

Constraints:

  • 1 <= nums.length <= 500
  • -10^5 <= nums[i] <= 10^5
💡 Hints & Approach

Key Insight: Every single-element subarray is centered (sum = element). For longer subarrays, check if sum exists in the subarray.

Hint 1: All n single-element subarrays are automatically centered.

Hint 2: For subarrays of length >= 2, compute sum and check if any element equals the sum.

Hint 3: With n <= 500, O(n²) or O(n³) solutions are acceptable.

Approach:

  1. Start with count = n (all single elements are centered)
  2. For each subarray [i, j], compute sum and check if sum is in the subarray
  3. Use a set for O(1) lookup of elements in subarray
def countCenteredSubarrays(nums):
  n = len(nums)
  count = n  # All single elements are centered

  for i in range(n):
    elements = set()
    total = 0
    for j in range(i, n):
      elements.add(nums[j])
      total += nums[j]
      if j > i and total in elements:  # Length >= 2
        count += 1

  return count

Time Complexity: O(n²) Space Complexity: O(n)

Q3. Count Caesar Cipher Pairs

Field Value
Difficulty Medium
Points 4
Link LeetCode

Problem Description

You are given an array words of n strings. Each string has length m and contains only lowercase English letters.

Two strings s and t are similar if we can apply the following operation any number of times so that s and t become equal.

  • Choose either s or t.
  • Replace every letter in the chosen string with the next letter in the alphabet cyclically. The next letter after 'z' is 'a'.

Count the number of pairs of indices (i, j) such that:

  • i < j
  • words[i] and words[j] are similar.

Example 1:

Input: words = [“fusion”,”layout”]

Output: 1

Explanation:

words[0] = "fusion" and words[1] = "layout" are similar because we can apply the operation to "fusion" 6 times.

Constraints:

  • 1 <= n == words.length <= 10^5
  • 1 <= m == words[i].length <= 10^5
  • 1 <= n * m <= 10^5
💡 Hints & Approach

Key Insight: Two strings are similar if one is a cyclic shift of the other (in terms of character values).

Hint 1: Normalize each word to a canonical form. The difference pattern between adjacent characters is invariant under cyclic shifts.

Hint 2: Use (s[1]-s[0], s[2]-s[1], …, s[m-1]-s[m-2]) mod 26 as a signature.

Hint 3: Words with the same signature are similar. Count pairs with same signature.

Approach:

  1. For each word, compute its difference signature
  2. Use a hash map to count words with each signature
  3. For each group of k words with same signature, add C(k,2) = k*(k-1)/2 pairs
def countCaesarPairs(words):
  from collections import defaultdict

  def get_signature(word):
    # Compute difference pattern
    sig = []
    for i in range(1, len(word)):
      diff = (ord(word[i]) - ord(word[i-1])) % 26
      sig.append(diff)
    return tuple(sig)

  signature_count = defaultdict(int)
  for word in words:
    sig = get_signature(word)
    signature_count[sig] += 1

  total_pairs = 0
  for count in signature_count.values():
    total_pairs += count * (count - 1) // 2

  return total_pairs

Time Complexity: O(n * m) Space Complexity: O(n * m)

Q4. Maximum Bitwise AND After Increment Operations

Field Value
Difficulty Hard
Points 6
Link LeetCode

Problem Description

You are given an integer array nums and two integers k and m.

You may perform at most k operations. In one operation, you may choose any index i and increase nums[i] by 1.

Return an integer denoting the maximum possible bitwise AND of any subset of size m after performing up to k operations optimally.

Constraints:

  • 1 <= n == nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9
  • 1 <= m <= n
💡 Hints & Approach

Key Insight: Binary search on the answer. For a target AND value X, check if we can choose m elements and increment them to all have X as a prefix in their binary representation.

Hint 1: If the AND result is X, then all m chosen elements must have X as their “base” (all bits in X must be 1 in all elements).

Hint 2: For each candidate AND value X, check: can we make m elements all reach at least X, and all have the bits of X set?

Hint 3: Build the answer bit by bit from MSB to LSB, greedily trying to set each bit.

Approach:

  1. Try to construct answer bit by bit from highest to lowest
  2. For each bit position, try setting it and check if achievable
  3. To check: for target T, find m elements with minimum cost to reach T, where cost[i] = (T - nums[i]) if nums[i] <= T, else infinity
def maxBitwiseAnd(nums, k, m):
  n = len(nums)

  def can_achieve(target):
    # Can we pick m elements and make them all >= target
    # with bits of target all set, using at most k operations?
    costs = []
    for num in nums:
      if num > target:
        # Need to reach next multiple of target+1 that has all bits of target
        # This is complex - simplified: just check if all bits of target can be set
        # Actually: num AND target should equal target after incrementing
        # If num already has all bits of target set, cost = 0
        # Otherwise, we need to increment to next number with those bits
        pass
      # Simpler approach: cost to make num have AND with target == target
      # We need num to have at least all 1-bits of target
      if (num & target) == target:
        costs.append(0)
      else:
        # Need to increment until (num + delta) & target == target
        # This happens when num + delta >= target (approximately)
        delta = target - num if num < target else 0
        if num < target:
          costs.append(target - num)
        else:
          # num > target but missing some bits
          # Complex case - need to find smallest increment
          costs.append(float('inf'))

    costs.sort()
    return sum(costs[:m]) <= k

  # Binary search or greedy bit construction
  result = 0
  for bit in range(30, -1, -1):
    candidate = result | (1 << bit)
    if can_achieve(candidate):
      result = candidate

  return result

Simplified Approach:

def maxBitwiseAnd(nums, k, m):
  def min_cost_to_target(target):
    costs = []
    for num in nums:
      if num <= target:
        costs.append(target - num)
      else:
        # num > target, check if AND gives target
        if (num & target) == target:
          costs.append(0)
        else:
          costs.append(float('inf'))
    costs.sort()
    return sum(costs[:m])

  result = 0
  for bit in range(30, -1, -1):
    candidate = result | (1 << bit)
    if min_cost_to_target(candidate) <= k:
      result = candidate

  return result

Time Complexity: O(n * 30 * log n) = O(n log n) Space Complexity: O(n)