1513. Number of Substrings With Only 1s

GENERAL APPROACH

We scan the string once from left to right.
We count how many consecutive '1' characters appear in a row.

• If the character is '1', increase the current streak count.
• If the character is '0', compute the number of substrings formed by the previous streak of ones:

=> (k⋅(k+1))/2

Then reset the counter.

At the end, we add the contribution of the last streak.

This approach is optimal with O(n) time and O(1) space.

Hindi

हम स्ट्रिंग को left से right एक बार scan करते हैं।
जहाँ भी लगातार '1' आते हैं, हम उनकी गिनती (streak) बढ़ाते जाते हैं।

• अगर character '1' है → count बढ़ाएँ।
• अगर character '0' है → पिछले लगातार '1' से बनने वाले substring की संख्या निकालें:

=> (k⋅(k+1))/2

फिर count को 0 कर दें।

अंत में, आख़िरी '1' की streak का result भी जोड़ देते हैं।

यह तरीका O(n) समय और O(1) स्थान में सबसे optimal है।

Python Solution:

class Solution:
    def numSub(self, s: str) -> int:
        mod = 10**9 + 7
        count = 0
        result = 0
        
        for ch in s:
            if ch == '1':
                count += 1
            else:
                result = (result + count * (count + 1) // 2) % mod
                count = 0
        
        # Add last run
        result = (result + count * (count + 1) // 2) % mod
        
        return result

C++ Solution:

class Solution {
public:
    int numSub(string s) {
        const long long MOD = 1e9 + 7;
        long long count = 0, result = 0;

        for(char c : s) {
            if(c == '1') {
                count++;
            } else {
                result = (result + count * (count + 1) / 2) % MOD;
                count = 0;
            }
        }

        result = (result + count * (count + 1) / 2) % MOD;
        return result;
    }
};

Java Solution:

class Solution {
    public int numSub(String s) {
        long MOD = 1_000_000_007;
        long count = 0, result = 0;

        for(char c : s.toCharArray()) {
            if(c == '1') {
                count++;
            } else {
                result = (result + count * (count + 1) / 2) % MOD;
                count = 0;
            }
        }

        result = (result + count * (count + 1) / 2) % MOD;
        return (int) result;
    }
}

Summary :

We scan the string once and count consecutive runs of '1'.
Each run contributes:

1+2+⋯+k=(k(k+1))/2

This is the optimal solution.

Final Complexity Table

Case	Identity	Time Complexity	Space Complexity
Best	All 0s	O(n)	O(1)
Average	Mix of 0s and 1s	O(n)	O(1)
Worst	All 1s	O(n)	O(1)