Medium LC Problem in Python

-

This is my first medium-difficulty LC problem in Python (learning the language). It still does not require any deep understand of the language (only simple data structures), just the basics loops and conditions. Here is the problem: https://leetcode.com/problems/number-of-ways-to-split-a-string/

1573. Number of Ways to Split a String
Medium

Given a binary string s (a string consisting only of '0's and '1's), we can split s into 3 non-empty strings s1, s2, s3 (s1+ s2+ s3 = s).

Return the number of ways s can be split such that the number of characters '1' is the same in s1, s2, and s3.

Since the answer may be too large, return it modulo 10^9 + 7.

 

Example 1:

Input: s = "10101"
Output: 4
Explanation: There are four ways to split s in 3 parts where each part contain the same number of letters '1'.
"1|010|1"
"1|01|01"
"10|10|1"
"10|1|01"

Example 2:

Input: s = "1001"
Output: 0

Example 3:

Input: s = "0000"
Output: 3
Explanation: There are three ways to split s in 3 parts.
"0|0|00"
"0|00|0"
"00|0|0"

Example 4:

Input: s = "100100010100110"
Output: 12

 

Constraints:

  • s[i] == '0' or s[i] == '1'
  • 3 <= s.length <= 10^5

The logic is actually pretty straightforward after some initial investigation:
 - If the string length is less than 3, return 0
 - If it does not contain 1s, just do a combinatorial
 - Else, find the zeros in between the blocks, add one, and multiply the result, always "mod"ing it

Code is below, cheers, ACC.


    def numWays(self, s):
        #count the number of 1s and return it
        numberOnes = 0
        for i in range(len(s)):
            if s[i] == '1':
                numberOnes += 1
        
        #if zero, simple combinatorial
        if numberOnes == 0:
            if len(s) < 3:
                return 0
            return int((((len(s) - 1)*(len(s) - 2))/2) % 1000000007)

        #not multiple of 3, bail
        if numberOnes % 3 != 0:
            return 0

        #solution is the multiplication of number of zeros (plus 1) in between the blocks
        index1 = numberOnes/3
        countBlock1 = 0
        insideBlock1 = False
        index2 = 2*index1
        countBlock2 = 0
        insideBlock2 = False

        countOnes = 0
        for i in range(len(s)):
            if s[i] == '1':
                countOnes += 1
            if not insideBlock1 and countOnes == index1:
                insideBlock1 = True
                continue
            if countOnes == index1 + 1:
                insideBlock1 = False
            if not insideBlock2 and countOnes == index2:
                insideBlock2 = True
                continue
            if countOnes == index2 + 1:
                insideBlock2 = False

            if insideBlock1:
                countBlock1 += 1
            if insideBlock2:
                countBlock2 += 1

        return int(((countBlock1 + 1) * (countBlock2 + 1)) % 1000000007)

Comments

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more