LeetCode Entry

76. Minimum Window Substring

04.02.2024 hard 2024 kotlin rust

Let's try to shorten the code

76. Minimum Window Substring hard blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/495

Problem TLDR

Minimum window of s including all chars of t.

Intuition

The greedy approach with sliding window would work: move right window pointer right until all chars are obtained. Then move left border until condition no longer met.

There is an optimization possible: remove the need to check all character’s frequencies by counting how many chars are absent.

Approach

Let’s try to shorten the code:

  • .drop.take is shorter than substring, as skipping one if
  • range in Rust are nice
  • into shortern than to_string

Complexity

  • Time complexity: \(O(n + m)\)

  • Space complexity: \(O(1)\)

Code


  fun minWindow(s: String, t: String): String {
    val freq = IntArray(128)
    for (c in t) freq[c.code]++
    var i = 0
    var r = arrayOf(s.length, s.length + 1)
    var count = t.length
    for ((j, c) in s.withIndex()) {
      if (freq[c.code]-- > 0) count--
      while (count == 0) {
        if (j - i + 1 < r[1]) r = arrayOf(i, j - i + 1)
        if (freq[s[i++].code]++ == 0) count++
      }
    }
    return s.drop(r[0]).take(r[1])
  }



  pub fn min_window(s: String, t: String) -> String {
    let mut freq = vec![0; 128];
    for b in t.bytes() { freq[b as usize] += 1; }
    let (mut i, mut r, mut c) = (0, 0..0, t.len());
    for (j, b) in s.bytes().enumerate() {
      if freq[b as usize] > 0 { c -= 1; }
      freq[b as usize] -= 1;
      while c == 0 {
        if j - i + 1 < r.len() || r.len() == 0 { r = i..j + 1; }
        let a = s.as_bytes()[i] as usize;
        freq[a] += 1; if freq[a] > 0 { c += 1; }
        i += 1;
      }
    }
    s[r].into()
  }