Minimum Number of Changes to Make Binary String Beautiful — LeetCode 2914 Python Solution
MediumString
- Problem
- #2914
- Pattern
- Hash Map
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given a 0-indexed binary string s having an even length. A string is beautiful if it's possible to partition it into one or more substrings such that: Each substring has an even length.
Example
- Input
- s = "1001"
- Output
- 2
- Explanation
- We change s[1] to 1 and s[3] to 0 to get string "1100".
Python solution
Python
class Solution:
def minChanges(self, s: str) -> int:
return sum(s[i] != s[i - 1] for i in range(1, len(s), 2))Complexity
| Measure | Complexity |
|---|---|
| Time | O(n), where n is the length of the string s |
| Space | O(1) auxiliary |
Pattern: Hash Map
Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 2914. Minimum Number of Changes to Make Binary String Beautiful is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2914. Minimum Number of Changes to Make Binary String Beautiful?
- LeetCode 2914. Minimum Number of Changes to Make Binary String Beautiful is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2914. Minimum Number of Changes to Make Binary String Beautiful?
- The Python solution on this page runs in O(n), where n is the length of the string s.
- What is the space complexity of LeetCode 2914. Minimum Number of Changes to Make Binary String Beautiful?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2914. Minimum Number of Changes to Make Binary String Beautiful cover?
- LeetCode 2914. Minimum Number of Changes to Make Binary String Beautiful is tagged String on LeetCode.