Count number of valid substring in binary string
This algorithm to count number of valid substring in given binary string.
Valid substrings will be 01, 10, 0011, 1100, 000111, 111000, 00001111, 11110000 …. etc
Example :
Input : 0001000
Output : 1
In above example there are only two substrings are possible and they are 01 and 10
Input : 1000001
Output : 2
In above example two substrings are 10 and 01
Input : 1010101
Output : 6
Substrings are : 10, 01, 10, 01, 10, 01 total 6 (six)
Input : 000111000
Output : 4
Substrings are : 01, 10, 000111, 111000 total four.
Algorithm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
package com.omt.learn.algo; public class BinaryStringZOCount { public static void main(String[] args) { String s = "000111000"; System.out.println("Count:" + validCount(s)); } public static int validCount(String s) { int count = 0; for (int j = 1; j < s.length(); j++) { if (s.charAt(j - 1) != s.charAt(j)) { count++; if ((j - 1 > 0 && j + 1 < s.length()) && s.charAt(j - 1 - 1) != s.charAt(j + 1)) { count++; j++; } } } return count; } } |