# Links

Go to my solution

Go to the question on LeetCode

# My Thoughts

**What Went Well**

I knew immediately what algorithm to use and how to implement it.

# Algorithm Description

**Sliding Window Technique -** An algorithm that takes a subset of data from an iterable object and expands or reduces that subset based on given conditions.

**Visual Examples**

An intense dive into the sliding window technique can be found here, click to view

Unfortunately, all the other resources I found that spoke about the sliding window technique covered only some of its use cases.

# Solution Statistics

**Time Spent Coding**

5 minutes

**Time Complexity**

O(n) - In the worst-case scenario, each element gets visited twice, but since the increase in time is still linear, aka big O ignores content multiples of n, it still leaves us with an O(n) time complexity.

**Space Complexity**

O(n) - In the worst-case scenario, the entire string will be partitioned into equal parts of “large” groups making us store n/3 intervals, resulting in the O(n) space complexity because, as stated in the last problem, the increase in space usage is still linear despite it being divided by 3.

**Runtime Beats**

80.72% of other submissions

**Memory Beats**

98.80% of other sumbissions

# Solution

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

class Solution(object):
def largeGroupPositions(self, s):
if len(s) < 3: return []
# Left and right "pointers"
l, r = 0, 1
groups = []
while r < len(s):
# If the left and right characters match, continue as normal
# and skip the rest of the while loop
if s[l] == s[r]:
r += 1
continue
# If the left and right characters do NOT match, then check
# If the group is large, if it then appends it to the output list
if r-l > 2:
groups.append([l,r-1])
l = r
r += 1
# Edge case: Check for an extra group at the end of the while loop
if r-l > 2:
groups.append([l,r-1])
return groups