How hard is LeetCode 1375. Number of Times Binary String Is Prefix-Aligned?

LeetCode 1375. Number of Times Binary String Is Prefix-Aligned is rated Medium on LeetCode.

What is the time complexity of LeetCode 1375. Number of Times Binary String Is Prefix-Aligned?

The Python solution on this page runs in O(n), where n is the length of the array flips.

What is the space complexity of LeetCode 1375. Number of Times Binary String Is Prefix-Aligned?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 1375. Number of Times Binary String Is Prefix-Aligned cover?

LeetCode 1375. Number of Times Binary String Is Prefix-Aligned is tagged Array on LeetCode.

MediumNo. 1375

Number of Times Binary String Is Prefix-Aligned — LeetCode 1375 Python Solution

Topics: Array
Reading time: 2 min
Source: leetcode.com

The problem

You have a 1-indexed binary string of length n where all the bits are 0 initially. We will flip all the bits of this binary string (i.e., change them from 0 to 1) one by one.

Example

Input: flips = [3,2,4,1,5]
Output: 2
Explanation: The binary string is initially "00000".

Python solution

PythonSolution

class Solution:
    def numTimesAllBlue(self, flips: List[int]) -> int:
        ans = mx = 0
        for i, x in enumerate(flips, 1):
            mx = max(mx, x)
            ans += mx == i
        return ans

Complexity

Time: O(n)where n is the length of the array flips
Space · auxiliary: O(1)

Related problems
No.	Problem	Difficulty
0057	Insert Interval	Medium
0228	Summary Ranges	Easy
0485	Max Consecutive Ones	Easy
0665	Non-decreasing Array	Medium
0674	Longest Continuous Increasing Subsequence	Easy
0699	Falling Squares	Hard

Frequently asked questions

How hard is LeetCode 1375. Number of Times Binary String Is Prefix-Aligned?: LeetCode 1375. Number of Times Binary String Is Prefix-Aligned is rated Medium on LeetCode.
What is the time complexity of LeetCode 1375. Number of Times Binary String Is Prefix-Aligned?: The Python solution on this page runs in O(n), where n is the length of the array flips.
What is the space complexity of LeetCode 1375. Number of Times Binary String Is Prefix-Aligned?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1375. Number of Times Binary String Is Prefix-Aligned cover?: LeetCode 1375. Number of Times Binary String Is Prefix-Aligned is tagged Array on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Download for Mac Download for Windows

Free to download. Check it runs on your machine, then pick a plan.

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

Transcript

"Okay, next one. Given a string, return the length of the longest substring that has no repeating characters. Walk me through your approach before you code it."

Technical interview · 45 minsolution.pyShared editor · Python 3Longest substring without repeatsMediumGiven a string s, return the length of the longest contiguous substring in which every character is unique.s = "abcabcbb"
→ 31def length_of_longest_substring(s: str) -> int:2 last_seen = {}3 left = best = 04 for right, ch in enumerate(s):5 if ch in last_seen and last_seen[ch] >= left:

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 Terra

Transcribing...

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

Transcript

"Okay, next one. Given a string, return the length of the longest substring that has no repeating characters. Walk me through your approach before you code it."

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 TerraClear chat

Transcribing...

QuitEscHide+QCapture+PCrop+OSubmit+EnterPress to get answerLeft/Right+Up/Down+

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

Transcript

"Okay, next one. Given a string, return the length of the longest substring that has no repeating characters. Walk me through your approach before you code it."

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 TerraClear chat

Transcribing...

Primary display

QuitEscHide+QCapture+PCrop+OSubmit+EnterPress to get answerLeft/Right+Up/Down+

The problem

Example

Python solution

Complexity

Related problems

Frequently asked questions

Stuck on problems like this in a live interview?

Approach

Approach

Approach