Post date: Jul 05, 2013 10:24:22 PM
Problem
Given a ternary string, you have to count the total number of contiguous substrings (contigious set of characters), that you can form from this given string such that they comprise of either only one or two different characters.
Please note that a unique substring will be decided by its starting and ending indices. So, a substring 'ab' with starting and ending indices being 1 and 2 respectively should be considered different from a substring 'ab' with starting or ending indices (or both) other than 1 and 2 respectively.
For example:
input ternary string - aabc
output - 8
The above string comprises of the following substrings that have either one or two of the characters - a, a, b, c, aa, ab, bc and aab. So the final answer is a total of eight substrings.
input ternary string - abc
output - 5
The above string comprises of the following substrings that have either one or two of the characters - a, b, c, ab and bc. So the final answer is a total of five substrings.
input ternary string - baaccb
output - 16
The above string comprises of the following substrings that have either one or two of the characters - b, a, a, c, c, b, aa, cc, ba, ac, cb, baa, aac, acc, ccb and aacc. So the final answer is a total of sixteen substrings
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Count the total number of contiguous substrings
Created Date : 06-07-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <stack>
#include <vector>
#include <cassert>
#include <set>
#include <string>
using namespace std;
static int CountChars(string str)
{
set<char> s(str.begin(), str.end());
return s.size();
}
static int CountContiguousSubstrings(string str)
{
int cnt = 0;
int start = 0;
while (start < str.size())
{
int subLen = 1;
while((start + subLen - 1 < str.size()) && CountChars(str.substr(start, subLen)) < 3){
cout << (str.substr(start, subLen)) << endl;
subLen ++;
cnt ++;
}
start ++;
}
return cnt;
}
static void DoTest(string str)
{
cout << "The ternary string is " << str << endl;
if (CountChars(str) > 3)
{
cout << "Invalid input string" << endl;
return;
}
cout << "The substrings are as follows: " << endl;
int count = CountContiguousSubstrings(str);
cout << "The are " << count << " substrings" << endl;;
cout << "-------------------------------" << endl;
}
int main(int argc, char* argv[])
{
DoTest("aabc");
DoTest("abc");
DoTest("baaccb");
DoTest("abcd");
return 0;
}
Output
The ternary string is aabc
The substrings are as follows:
a
aa
aab
a
ab
b
bc
c
The are 8 substrings
-------------------------------
The ternary string is abc
The substrings are as follows:
a
ab
b
bc
c
The are 5 substrings
-------------------------------
The ternary string is baaccb
The substrings are as follows:
b
ba
baa
a
aa
aac
aacc
a
ac
acc
c
cc
ccb
c
cb
b
The are 16 substrings
-------------------------------
The ternary string is abcd
Invalid input string
Press any key to continue . . .