1. Mở đầu

Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.

2. Đề bài

Link bài tập: Minimum Number of Steps to Make Two Strings Anagram

Bạn được cho hai chuỗi có cùng độ dài s và t. Trong một bước, bạn có thể chọn một ký tự bất kỳ trong t và thay thế nó bằng một ký tự khác.

Hãy trả về số bước tối thiểu để biến t thành một từ hoán vị của s.

Một từ hoán vị của một chuỗi là một chuỗi mà nó chứa cùng các ký tự với một thứ tự khác (hoặc có thể giống thứ tự).

Ví dụ 1:

Input: s = "bab", t = "aba"
Output: 1
Giải thích: Thay thế 'a' đầu tiên trong `t` bằng 'b', t = "bba" là một từ hoán vị của `s`.

Ví dụ 2:

Input: s = "leetcode", t = "practice"
Output: 5
Giải thích: Thay thế 'p', 'r', 'a', 'i' và 'c' từ `t` bằng các ký tự phù hợp để biến `t` thành một từ hoán vị của `s`.

Ví dụ 3:

Input: s = "anagram", t = "mangaar"
Output: 0
Giải thích: "anagram" và "mangaar" đã là từ hoán vị của nhau.

Ràng buộc:

  • 1 <= s.length <= 5 * 10^4
  • s.length == t.length
  • s và t chỉ chứa các ký tự tiếng Anh thường.

3. Phân tích

3.1. Gợi ý

Để giải bài này, ta cần đếm tần số xuất hiện của mỗi ký tự trong mỗi chuỗi.
Cấu trúc dữ liệu nào giúp ta làm được điều này?

  • Yep, đó chính là cấu trúc dữ liệu map, tuy nhiên điều kiện ràng buộc bài này thì chỉ có các ký tự tiếng Anh thường, tức là gói gọn trong 26 ký tự. Vậy nên ta cũng không cần dùng đến map mà có thể sử dụng slice với kích thước 26.

3.2. Ý tưởng

Ta sẽ tạo ra hai slice chứa tần số xuất hiện của các ký tự trong hai chuỗi s và t. Sau đó lấy tần số xuất hiện của ký tự trong s trừ đi t, nếu lớn hơn thì ta cộng dồn vào biến min chứa kết quả.
Kết quả trả về là biến min.

4. Code chạy bằng cơm

Hãy cùng xem ví dụ 2:

leet-code-1347-0

Đầu tiên ta sẽ lưu tần số xuất hiện các ký tự của hai chuỗi vào hai slice khác nhau:

leet-code-1347-1

Giờ ta chỉ cần kiểm tra xem tần số ký tự trong mảng s có lớn hơn mảng t không? Nếu có thì ta lấy tần số của cùng ký tự đó trong mảng s trừ đi tần số trong mảng t, cộng dồn các hiệu này lại là ra kết quả.

Ví dụ, ký tự 't' ở mảng s có 1, nhưng ở mảng t không có, như vậy hiệu của chúng là 1, ta cộng dồn vào biến min:
leet-code-1347-2

Ký tự 'e' cũng tương tự:
leet-code-1347-3

Ký tự 'o' cũng thế:
leet-code-1347-4

Cuối cùng là ký tự 'd':
leet-code-1347-5

Kết quả trả về là min.

5. Code bằng máy

Code Go của chúng ta như sau:

func minSteps(s string, t string) int {
    min := 0

    counts := [26]int{}
    countt := [26]int{}

    for _, v := range s {
        counts[v - 'a']++
    }

    for _, v := range t {
        countt[v - 'a']++
    }

    for i := 0; i < len(counts); i++ {
        gap := counts[i] - countt[i]
        if gap > 0 {
            min += gap
        }
    }

    return min
}

6. Kết thúc

Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!