Topcoder SRM 689 NonDeterministicSubstring

this problem is about

Problem Statement

     You are given two Strings: A and B. Each character in A is either '0' or '1'. Each character in B is '0', '1', or '?'.

A string C matches B if we can change B into C by changing each '?' in B either to '0' or to '1'. Different occurrences of '?' may be changed to different digits. For example, C = "0101" matches B = "01??". Note that each character in C must be either '0' or '1', there cannot be any '?' remaining.

Consider all possible strings that match B. How many of these strings occur as a (contiguous) substring in A? Compute and return their number. Note that we only count each good string once, even if it has multiple occurrences in A.


Class: NonDeterministicSubstring
Method: ways
Parameters: String, String
Returns: long
Method signature: long ways(String A, String B)
(be sure your method is public)


Time limit (s): 2.000
Memory limit (MB): 256
Stack limit (MB): 256


- A will contain between 1 and 50 characters, inclusive.
- B will contain between 1 and 50 characters, inclusive.
- Each character in A will be '0' or '1'.
- Each character in B will be '0', '1' or '?'.


Returns: 3
There are four strings that match B: the strings "00", "01", "10", and "11". Out of these, the string "11" does not occur in A as a substring. The other three do occur, hence the answer is 3.
Returns: 1
There are 16 different strings that match B, but out of those only the string "000000" is a substring of A.
Returns: 8
Each of the 8 strings that match B occurs somewhere in A.
Returns: 0
Here, the length of B is greater than the length of A. Clearly, a string that matches this B cannot be a substring of this A.
Returns: 6

My approach

1. A>B and
2. Find B length
3. Make all possible String with length of B and push HashSet
4. HashSet will filter duplication.
5. and finally only unique strings remain in hashset
6. compare all string with B if index of character is not ?
7. count all if it is match

my code is below
public long ways(String A, String B){
  HashSet<String> set = new HashSet<String>();
  int blen = B.length();
  for (int i = 0; i <= A.length()-blen; i++) {
   set.add(A.substring(i, i+blen));
  Iterator<String> iter =  set.iterator();
  int count =0;
  while (iter.hasNext()) {
   String str =;
   boolean found = true;   
   for (int i = 0; i < blen; i++) {
    if(B.charAt(i)!= '?'){
     if(A.charAt(i) != B.charAt(i)){
      found =false;
  return count;


Popular posts from this blog

codefights smooth sailing ( CommonCharacterCount)

Bucket Sort in python