String Advanced

Algorithms
sliding window, string
Catalogue
  1. 1. Sliding Window in a String
    1. 1.1. 3. Longest Substring Without Repeating Characters
    2. 1.2. 340. Longest Substring with At Most K Distinct Characters
    3. 1.3. 438. Find All Anagrams in a String
      1. 1.3.1. Sol1. Sort
      2. 1.3.2. Sol2.Sliding Window
    4. 1.4. Flip 0 to 1
  2. 2. Read4
    1. 2.1. 157. Read N Characters Given Read4
    2. 2.2. 158. Read N Characters Given Read4 II - Call multiple times

Sliding Window in a String

  • Hash table

3. Longest Substring Without Repeating Characters

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        visited = set()
        left = right = 0
        cnt = 0
        n = len(s)
        while right < n:
            if s[right] not in visited:
                visited.add(s[right])
                right += 1
                cnt = max(cnt, right-left)
            else:
                visited.remove(s[left])
                left += 1
        return cnt

###159. Longest Substring with At Most Two Distinct Characters

  • Two pointers: i - traversal, start - shrink to meet the condition!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def lengthOfLongestSubstringTwoDistinct(self, s):
        chars = [0] * 256
        start = 0
        res = cnt = 0
        for i in xrange(len(s)):
            idx = ord(s[i])
            if chars[idx] == 0:
                cnt += 1
            chars[idx] += 1

            while cnt > 2: # shrink
                idx = ord(s[start])
                chars[idx] -= 1
                if chars[idx] == 0:
                    cnt -= 1
                start += 1
            res = max(res, i-start+1)
        return res

340. Longest Substring with At Most K Distinct Characters

  • care about variables!!! always miss some statements
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        chars = [0] * 256
        start = 0
        res = cnt = 0
        for i in xrange(len(s)):
            idx = ord(s[i])
            if chars[idx] == 0:
                cnt += 1
            chars[idx] += 1

            while cnt > k:
                idx = ord(s[start])
                chars[idx] -= 1
                if chars[idx] == 0:
                    cnt -= 1
                start += 1
            res = max(res, i-start+1)
        return res

438. Find All Anagrams in a String

Sol1. Sort

Time : O(n m logm)

Sol2.Sliding Window

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
class Solution(object):
    def findAnagrams(self, s, p):
        m, n = len(s), len(p)

        char_dic = collections.defaultdict(int)
        cnt = 0

        # Init p : count char in p
        for ch in p:
            char_dic[ch] += 1
            if char_dic[ch] == 1:
                cnt += 1

        # Init sliding window
        for ch in s[:n]:
            if ch not in char_dic:
                continue

            char_dic[ch] -= 1
            if char_dic[ch] == 0:
                cnt -= 1

        res = []
        if cnt == 0:
            res.append(0)

        # move the Fixed size sliding window
        for i in xrange(m-n):
            if s[i] in char_dic:
                char_dic[s[i]] += 1
                if char_dic[s[i]] == 1:
                    cnt += 1
            if s[i+n] in char_dic:
                char_dic[s[i+n]] -= 1
                if char_dic[s[i+n]] == 0:
                    cnt -= 1
            if cnt == 0:
                res.append(i+1)

        return res

Flip 0 to 1

Given a 0-1 array, you can flip at most k ‘0’s to ‘1’s.Please find the longest subarray that consists of all ‘1’s.

  • Solution : Find a slinding window that contains at most k zeros.
  1. When to move the right border: when the counter of zeros <=k
  2. When to move the left border: when the counter of zeros >k
  • Clarify the information contains in the sliding window
  • when to move the pointer/border

Read4

157. Read N Characters Given Read4

  • fixed size 4 temp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def read(self, buf, n):
        cnt = 0
        while cnt < n:
            temp = [''] * 4
            rd = read4(temp)
            to_copy = min(rd, n-cnt)
            for i in range(to_copy):
                buf[cnt] = temp[i]
                cnt += 1

            if to_copy == 0:
                return cnt
        return cnt

158. Read N Characters Given Read4 II - Call multiple times

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def __init__(self):
        self.queue = collections.deque()

    def read(self, buf, n):
        cnt = 0
        queue = self.queue
        while queue and cnt < n:
            buf[cnt] = queue.popleft()
            cnt += 1

        while cnt < n:
            temp = [''] * 4
            rd = read4(temp)
            for i in range(rd):
                queue.append(temp[i])

            k = min(rd, n-cnt)
            for _ in range(k):
                buf[cnt] = self.queue.popleft()
                cnt += 1
            if k == 0:
                return cnt
        return cnt
Share