LeetCode Number of Substrings Containing All Three Characters: Sliding Window in Golang

Ehab Hosam — Tue, 11 Mar 2025 13:12:50 +0000

Today's LeetCode daily challenge was so fun to solve: Number of
Substrings Containing All Three Characters.

What are we trying to do?

We have a string s that's build using only 3 characters: a, b and c. We wanna know how many substrings in it that has the a, b and c at the same time.

Once you read the description of the problem, and if you know the Sliding window technique, you'll immediately know that this problem has to be solved using a sliding window. It's of course normal to not get the efficient solution if it's your first time to hear about that technique.

A sliding window ... Let's break it down.

It's implemented with 2 pointers: high & low. There is always a condition that you want to achieve, which is to contain all the 3 characters at our problem. To track if we are meeting the condition, we maintain a map that counts how many times did each letter occur in the current substring. We also need a counter variable to increment when we meet our condition.

Both pointers start at first letter.

We move the high pointer to the right until we meet the condition.

Met the condition? Increment the counter, but how much should we increment it? In the example shown in the image, the substring "abc" meets our condition, where the 3 letters exist in it. Do we increment by 1? of course no. Wherever the high pointer goes, it will still meet the condition, as you're just adding more letters to the string, so it will always have the "abc" followed by any sequence of letters. So here the "abc", "abca", "abcab" and "abcabc" (4 strings) meet our condition. How to reach that 4? Easy. Subtract the position of the high pointer from the length of the whole string. result += length(string) - high

After incrementing the result, start moving the Low pointer to the right, which cuts from the start of our substring. If you still meet the condition, increment the result again and do so until the condition isn't met, then you start moving the high again.

Continue this process until the high pointer reaches the last letter of the string, and then we'll have the number we're looking for stored in the result variable.

Implementation

We make a custom map that has the methods we are going to use. The map has 3 properties a, b and c, and it has 3 methods:

NewMap: aka constructor.
Push: adds a letter (increments its counter)
Pop: removes a letter (decrements its counter)
IsValid: checks if the current state of the map meets our condition (checks if the 3 letters are present in the current substring).

Code

package main

import (
    "fmt"
)

type Map struct {
    a, b, c int
}

func NewMap() *Map {
    return &Map{}
}

func (m *Map) Push(key byte) {
    switch key {
    case 'a':
        m.a++
    case 'b':
        m.b++
    case 'c':
        m.c++
    }
}

func (m *Map) Pop(key byte) {
    switch key {
    case 'a':
        m.a--
    case 'b':
        m.b--
    case 'c':
        m.c--
    }
}

func (m *Map) IsValid() bool {
    return m.a > 0 && m.b > 0 && m.c > 0
}

func numberOfSubstrings(s string) int {
    occurrences := NewMap()
    result := 0
    low := 0

    for high := range s {
        occurrences.Push(s[high])
        for occurrences.IsValid() {
            result += len(s) - high
            occurrences.Pop(s[low])
            low++
        }
    }

    return result
}



func main() {
    case1 := numberOfSubstrings("abcabc")
    case2 := numberOfSubstrings("aaacb")
    case3 := numberOfSubstrings("abc")
    fmt.Println(case1)
    fmt.Println(case2)
    fmt.Println(case3)
}

See you soon in another challenge :)

LeetCode in Golang: Parsing A Boolean Expression

Ehab Hosam — Mon, 21 Oct 2024 09:09:56 +0000

This is one of the LeetCode problems I enjoyed solving. I solved it in Golang, and I'm already a Go newbie, who started learning in it since just one week.

LeetCode: Parsing Boolean Expression (Hard)

Intuition

This problem is another version of implementing a calculator program that takes a string and evaluates it. You have to solve by evaluating the inner parenthesis to the outer ones until you get the final result. These problems are best described by a stack, you're just implementing a CallStack that when opening a new parenthesis, you Push to the stack, and when closing it you just Pop from the stack. At the last closing we call Eval to get the final result.

We have 3 operations that can be done in our calculator, and there are some known facts about them:

AND: it's true until you find a false (one false is enough)
OR: it's false until you find a true (one true is enough)
Not: it's the opposite of the it's argument.

So, we don't need to maintain all the values for each operation to know it's final result. If we're solving an AND, just maintain if you found a false or not, if OR, maintain if you found a true or not, and if NOT, then it's already gonna be one value that you'll evaluate to it's opposite one.

Approach

We implement a custom struct: CallStack, that has 2 slices, one for the operation and one for the value that we're gonna evaluate.
The call stack has methods:

Push: used to push values & operations to the 2 slices we have. Operations push new value to the 2 slices, and values (t or f) just modify the last entered value in the values slice.
Pop: remove last value from the 2 slices, evaluate the popped value with the popped operation and use the result to modify the new last value after popping.
Eval: called when it's the last closing parenthesis to evaluate the last remaining value in the values slice with the last remaining operation in the operations slice.

The solution can be more optimized by ending the evaluation of Ands once you find a false, and Ors once you find a true, I'll leave that for you to do if you want :)

Complexity

Time complexity:
O(n)
Space complexity:
O(n)

Code


type CallStack struct {
    operations []string
    values []int
}

func NewCallStack() *CallStack {
    return &CallStack{
        operations: make([]string, 0),
        values:     make([]int, 0),
    }
}

func (s *CallStack) pushOperation(op string) {
    s.operations = append(s.operations, op)
    var newVal int 
    switch op {
    case Not: 
        newVal = 0
    default: 
        newVal = 1
    }
    s.values = append(s.values, newVal)
}

func (s *CallStack) pushValue(op string, char string) {
    switch op {
    case And: 
        if char == "f" {
            s.values[len(s.values)-1] = -1
        } 
    case Or: 
        if char == "t" {
            s.values[len(s.values)-1] = -1
        } 
    default: // Not
        if char == "t" {
            s.values[len(s.values)-1] = 1
        } else {
            s.values[len(s.values)-1] = -1
        }
    }
}

func (s *CallStack) Push(char string) {
    switch char {
    case Not, And, Or:
        s.pushOperation(char)
    default:
        s.pushValue(s.operations[len(s.operations) - 1], char)
    }
}

func eval(op string, val int) bool {
    switch op {
    case And:
        if val == 1 {
            return true
        } else {
            return false
        }
    case Or:
        if val == -1 {
            return true
        } else {
            return false
        } 
    default: // Not 
        if val < 0 {
            return true
        } else {
            return false 
        }
    }
}

func addResult(op string, val int, res bool) int {
    switch op {
    case And:
        if res {
            return val
        } else {
            return -1
        }
    case Or:
        if res {
            return -1
        } else {
            return val
        } 
    default: // Not 
        if res {
            return 1
        } else {
            return -1 
        }
    } 
}

func (s *CallStack) Pop() {
    op := s.operations[len(s.operations)-1]
    s.operations = s.operations[:len(s.operations)-1]
    val := s.values[len(s.values)-1]
    s.values = s.values[:len(s.values)-1]

    result := eval(op, val)
    currOp := s.operations[len(s.operations)-1] // current last operation
    currVal :=  s.values[len(s.values)-1] // current last value 
    s.values[len(s.values)-1] = addResult(currOp, currVal, result)
}   

func (s *CallStack) Eval() bool {
    // now the length of slices is 1
    op := s.operations[0]
    val := s.values[0]
    return eval(op, val)
}

const (
    Not string = "!"
    And string = "&"
    Or  string = "|"
)

func parseBoolExpr(expression string) bool {
    stack := NewCallStack()

    for i := 0; i < len(expression); i++ {
        char := string(expression[i])
        switch char {
        case "(", ",": 
            // ignore opennings & commas
            continue 
        case ")": 
            if i == len(expression) - 1 {
                // it's the last closing 
                return stack.Eval()
            } else {
                stack.Pop()
            }
        default:
            stack.Push(char)
        }
    }
    return true
}

DEV Community: Ehab Hosam

LeetCode Number of Substrings Containing All Three Characters: Sliding Window in Golang

What are we trying to do?

A sliding window ... Let's break it down.

Implementation

Code

LeetCode in Golang: Parsing A Boolean Expression

Intuition

Approach

Complexity

Code