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: 0
Constraints:
s[i] == '0'ors[i] == '1'1 <= s.length <= 10^5
Solution: DP / Prefix Sum
dp[i] := # of all 1 subarrays end with s[i].
dp[i] = dp[i-1] if s[i] == ‘1‘ else 0
ans = sum(dp)
s=1101
dp[0] = 1 // 1
dp[1] = 2 // 11, *1
dp[2] = 0 // None
dp[3] = 1 // ***1
ans = 1 + 2 + 1 = 5
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: int numSub(string s) { constexpr int kMod = 1e9 + 7; long ans = 0; vector<int> dp(s.length() + 1); for (int i = 1; i <= s.length(); ++i) { dp[i] = s[i - 1] == '1' ? dp[i - 1] + 1 : 0; ans += dp[i]; } return ans % kMod; } }; |
dp[i] only depends on dp[i-1], we can reduce the space complexity to O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: int numSub(string s) { constexpr int kMod = 1e9 + 7; long ans = 0; int cur = 0; for (char c : s) { cur = c == '1' ? cur + 1 : 0; ans += cur; } return ans % kMod; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public int numSub(String s) { final int kMod = 1_000_000_000 + 7; int ans = 0; int cur = 0; for (int i = 0; i < s.length(); ++i) { cur = s.charAt(i) == '1' ? cur + 1 : 0; ans = (ans + cur) % kMod; } return ans; } } |
Python3
|
1 2 3 4 5 6 7 8 9 |
class Solution: def numSub(self, s: str) -> int: kMod = 10**9 + 7 ans = 0 cur = 0 for c in s: cur = cur + 1 if c == '1' else 0 ans += cur return ans % kMod |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment