MediumNo. 1525
Number of Good Ways to Split a String — LeetCode 1525 Python Solution
- Pattern
- Bit Manipulation
- Topics
- Bit Manipulation, Hash Table, String, Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given a string s. A split is called good if you can split s into two non-empty strings sleft and sright where their concatenation is equal to s (i.e., sleft + sright = s) and the number of distinct letters in sleft and sright is the same.
Example
- Input
- s = "aacaba"
- Output
- 2
- Explanation
- There are 5 ways to split "aacaba" and 2 of them are good.
Python solution
class Solution:
def numSplits(self, s: str) -> int:
cnt = Counter(s)
vis = set()
ans = 0
for c in s:
vis.add(c)
cnt[c] -= 1
if cnt[c] == 0:
cnt.pop(c)
ans += len(vis) == len(cnt)
return ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Bit Manipulation
Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 1525. Number of Good Ways to Split a String is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.
The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0691 | Stickers to Spell Word | Hard |
| 1255 | Maximum Score Words Formed by Letters | Hard |
| 0139 | Word Break | Medium |
| 0140 | Word Break II | Hard |
| 0187 | Repeated DNA Sequences | Medium |
| 0389 | Find the Difference | Easy |
Frequently asked questions
- How hard is LeetCode 1525. Number of Good Ways to Split a String?
LeetCode 1525. Number of Good Ways to Split a String is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1525. Number of Good Ways to Split a String?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1525. Number of Good Ways to Split a String?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1525. Number of Good Ways to Split a String cover?
LeetCode 1525. Number of Good Ways to Split a String is tagged Bit Manipulation, Hash Table, String and Dynamic Programming on LeetCode.