CareerCup

Find total = n(n-1)/2 , where n is the number of characters in the string. This gives the number of all continous substrings.

consider i=1, calculate an end point (which will be lesser than n) till which the condition is satisfied(string([i,i+1],string[i,i+2],.....string[i,end] will satisfy the condition). Find (n-end) and subract it from total. Now increment the value of i and start finding the same end , but need not start from i+1 to find the end, but can start from the previous 'end' found. Do this till i reaches n.

build a sliding window and track the running character number. O(n) time O(1) space

use suffix trees and then do dfs till u get third unique character ?

def collect_contig_substring(input_lst):
  result = []
  collect_contig_substring_given_chars(input_lst, {'a': True, 'b': False, 'c': False}, result)
  collect_contig_substring_given_chars(input_lst, {'a': False, 'b': True, 'c': False}, result)
  collect_contig_substring_given_chars(input_lst, {'a': False, 'b': False, 'c': True}, result)
  collect_contig_substring_given_chars(input_lst, {'a': True, 'b': True, 'c': False}, result)
  collect_contig_substring_given_chars(input_lst, {'a': False, 'b': True, 'c': True}, result)
  collect_contig_substring_given_chars(input_lst, {'a': True, 'b': False, 'c': True}, result)
  collect_contig_substring_given_chars(input_lst, {'a': True, 'b': True, 'c': True}, result)

  return result


def collect_contig_substring_given_chars(input_lst, ctrl_table,  result):
  n = len(input_lst)
  start = 0
  while start < n:
    if not ctrl_table[input_lst[start]]:
        continue;
    else:
        last_result = ''
        for i in range(start, n):
          if ctrl_table[input_lst[i]]:
            result.append(last_result + input_lst[i])
            last_result = result[len(result) - 1]
          else:
            start = i + 1
            break

@Shen Li, can you please explain your code's algo?

/** BFS ?
	 * @param char[] word
	 * @param int span = word.length-1
	 * @return
	 */
	public int getSubStrings(char[] word, int span){		
		if(!(span >=0))return 0;
		int counter=0;
		for(int i=0; (i+span)<=word.length-1;i++){			
			/*for(int j =i; j <= (i+span); j++){
				System.out.print(word[j]);
			}System.out.println();*/
			counter++;
		}
		--span;
		return counter+getSubStrings(word, span);		
	}

#include <iostream>
#include <string>
using namespace std;

int main(){
	string input_string;
	cin>>input_string;
	int count=0;
	for(int start=0;start<input_string.size();start++){
		++count;
		//cout<<input_string.substr(start,1)<<" ";
		char dif_char=' ';
		for(int end=start+1;end<input_string.size();end++){
			if(dif_char==' '){
				if(input_string[end]==input_string[start]){
					++count;
					//cout<<input_string.substr(start,end-start+1)<<" ";
				}else{
					++count;
					dif_char=input_string[end];
					//cout<<input_string.substr(start,end-start+1)<<" ";
				}
			}
			else if(input_string[end]==input_string[start]||
				input_string[end]==dif_char){
					++count;
					//cout<<input_string.substr(start,end-start+1)<<" ";
			}
			else
				break;
		}
	}

	cout<<count<<endl;
	return 0;
}

You morons, stop posting code. Discuss algo first.

int totalSubstring(char*x, int n)
{
if(n==0)
return 1;
int length=2, i=n-1;
while(i>1&&x[i-1]==x[i-2])
{
length++;
i--;
}
length=length+totalSubstring(x,n-1);
return length;
}

The idea if very simple and is based on counting a number of unique chars in a string.
1) Start from str[0] and add it to the set of unique characters.
2) Keep checking following characters till number of unique character is <=2
each time increment a counter of substrings
3) if number of unique characters in current substring is == 3 break a loop and repeat from go to 1) a start new iteration from str[1]

public class ContiguousSubString {

    public static void main(String[] args) {

	String s = "BAACCB";
	//String s = "ABC";
	Set<Character> uniqueChars = new HashSet<Character>();
	int counter = 0;
	for (int i = 0; i < s.length(); i++) {
	    uniqueChars.clear();
	    uniqueChars.add(s.charAt(i));
	    counter++;
	    System.out.println(s.charAt(i));
	    for (int j = i + 1; j < s.length(); j++) {
		if(!uniqueChars.contains(s.charAt(j))) {
		    uniqueChars.add(s.charAt(j));
		    if(uniqueChars.size() == 3) {
			break;
		    }
		}
		counter++;
		System.out.println(s.substring(i,j+1));
	    }
	}
	System.out.println("Total: "+counter);
    }
}