algorithms/leetcode/1910-RemoveAllOccurrencesOfASubstring.go at master · freewu/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
package main

// 1910. Remove All Occurrences of a Substring
// Given two strings s and part, perform the following operation on s until all occurrences of the substring part are removed:
//     Find the leftmost occurrence of the substring part and remove it from s.

// Return s after removing all occurrences of part.

// A substring is a contiguous sequence of characters in a string.

// Example 1:
// Input: s = "daabcbaabcbc", part = "abc"
// Output: "dab"
// Explanation: The following operations are done:
// - s = "daabcbaabcbc", remove "abc" starting at index 2, so s = "dabaabcbc".
// - s = "dabaabcbc", remove "abc" starting at index 4, so s = "dababc".
// - s = "dababc", remove "abc" starting at index 3, so s = "dab".
// Now s has no occurrences of "abc".

// Example 2:
// Input: s = "axxxxyyyyb", part = "xy"
// Output: "ab"
// Explanation: The following operations are done:
// - s = "axxxxyyyyb", remove "xy" starting at index 4 so s = "axxxyyyb".
// - s = "axxxyyyb", remove "xy" starting at index 3 so s = "axxyyb".
// - s = "axxyyb", remove "xy" starting at index 2 so s = "axyb".
// - s = "axyb", remove "xy" starting at index 1 so s = "ab".
// Now s has no occurrences of "xy".

// Constraints:
//     1 <= s.length <= 1000
//     1 <= part.length <= 1000
//     s and part consists of lowercase English letters.

import "fmt"
import "strings"

func removeOccurrences(s string, part string) string {
    res, n := []rune{}, len(part)
    for _, c := range s {
        res = append(res, c)
        if len(res) >= n {
            if string(res[len(res) - n:]) == part {
                res = res[:len(res) - n]
            }
        }
    }
    return string(res)
}

func removeOccurrences1(s string, part string) string {
    for strings.Contains(s, part) {
        s = strings.Replace(s, part, "", 1)
    }
    return s
}

func main() {
    // Example 1:
    // Input: s = "daabcbaabcbc", part = "abc"
    // Output: "dab"
    // Explanation: The following operations are done:
    // - s = "daabcbaabcbc", remove "abc" starting at index 2, so s = "dabaabcbc".
    // - s = "dabaabcbc", remove "abc" starting at index 4, so s = "dababc".
    // - s = "dababc", remove "abc" starting at index 3, so s = "dab".
    // Now s has no occurrences of "abc".
    fmt.Println(removeOccurrences("daabcbaabcbc", "abc")) // "dab"
    // Example 2:
    // Input: s = "axxxxyyyyb", part = "xy"
    // Output: "ab"
    // Explanation: The following operations are done:
    // - s = "axxxxyyyyb", remove "xy" starting at index 4 so s = "axxxyyyb".
    // - s = "axxxyyyb", remove "xy" starting at index 3 so s = "axxyyb".
    // - s = "axxyyb", remove "xy" starting at index 2 so s = "axyb".
    // - s = "axyb", remove "xy" starting at index 1 so s = "ab".
    // Now s has no occurrences of "xy".
    fmt.Println(removeOccurrences("axxxxyyyyb", "xy")) // "ab"

    fmt.Println(removeOccurrences1("daabcbaabcbc", "abc")) // "dab"
    fmt.Println(removeOccurrences1("axxxxyyyyb", "xy")) // "ab"
}