Algorithm to Count the Number of Substrings With Only 1s
- 时间:2020-10-11 15:25:20
- 分类:网络文摘
- 阅读:148 次
Given a binary string s (a string consisting only of ‘0’ and ‘1’s). Return the number of substrings with all characters 1’s. Since the answer may be too large, return it modulo 10^9 + 7.
Example 1:
Input: s = “0110111”
Output: 9
Explanation: There are 9 substring in total with only 1’s characters.“1” -> 5 times.
“11” -> 3 times.
“111” -> 1 time.Example 2:
Input: s = “101”
Output: 2
Explanation: Substring “1” is shown 2 times in s.Example 3:
Input: s = “111111”
Output: 21
Explanation: Each substring contains only 1’s characters.Example 4:
Input: s = “000”
Output: 0Constraints:
s[i] == ‘0’ or s[i] == ‘1’
1 <= s.length <= 10^5Hints:
Count number of 1s in each consecutive-1 group. For a group with n consecutive 1s, the total contribution of it to the final answer is (n + 1) * n // 2.
Count the Number of Substrings With Only 1s
Given a string that is size of n and contains only consecutive-ones, the total contribution to the final answer is (n+1)*n//2. Thus, we can split the origin string by ‘0’, then sum up the each individuals.
1 2 3 4 5 6 7 | class Solution: def numSub(self, s: str) -> int: arr = s.split('0') res = 0 for i in arr: res += (len(i) + 1) * len(i) // 2 return int(res % (1e9 + 7)) |
class Solution:
def numSub(self, s: str) -> int:
arr = s.split('0')
res = 0
for i in arr:
res += (len(i) + 1) * len(i) // 2
return int(res % (1e9 + 7))This (Math Solution) is far superior than the bruteforce algorithm where you enumerate all pairs in O(N^2) quadric time of substrings and check if each substring contains only 1’s (which will take O(N^3) all together).
The above solution runs at O(N) time and O(N) space – i.e. space required for spliting a string.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:5 Healthy Lifestyle Blogs to Know This 2020 Young People Changing the World One Idea at a Time Remember Your Blog Is A Reflection Of You Learn About Blog Content Planning Adding PHPUnit Tests for Discord Cryptocurrency Bot Regarding th Algorithm to Multiply Two Big Integers (String) Use jQuery Migrate Helper Plugin to Fix the Classic Editor Error How to Fix CloudFlare Error 1101 (Worker threw exception)? Python Function to Convert Excel Sheet Column Titles to Numbers Algorithm to Find the Kth Missing Positive Number in Array
- 评论列表
-
- 添加评论