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; } } |