Facebook Interview Question
Software Engineer / Developers Front-end Software EngineersCountry: India
I could not understand why will you pick 'a' as it is not present in input string 'bcd' ?
We don't need to use only the letters of the input string. The problem asks for *all* sstrings lexicographically smaller or equal than the input. Example "aba" or "abc" are 2 of 653 sstrings smaller or equal than "bcd"
DP here is redundant.
You can just calculate the result in this way:
static int MOD = 1009;
static int CalcSstring(string s)
{
int[] a = new int[s.Length];
a[0] = 1;
for (int i = 1; i < a.Length; i++)
{
a[i] = (a[i - 1] * 25) % MOD;
}
int result = 0;
for (int i = 0; i < s.Length; i++)
{
for (char ch = 'a'; ch < s[i]; ch++)
{
if (i > 0 && s[i - 1] == ch) continue;
result = (result + a[s.Length - i - 1]) % MOD;
}
}
return (result + 1) % MOD;
}
Similarly to what Zuzu mentioned, I don't think you need DP as there are no overlapping problems, furthermore, you can substitute your for loop for a simple multiplication:
int base = str[i] - 'a';
if (base > prev) // There will be one character to be skipped within the former loop
base = base - 1;
dp[i][prev] += base * sstrings[len-i-1];
I think this is your same solution except I only use backtracking without DP:
#define MOD 1009
int mod_pow(const uint& power)
{
if (power == 0)
return 1;
int result = 25;
for (int power_index = 1; power_index < power; power_index++)
result = (result * 25) % MOD;
return result;
}
int count_sstrings(char* text, const uint& text_size, const int& text_index)
{
int char_index = text[text_index] - 'a';
if (text_index == text_size - 1)
return char_index;
int base_count = char_index;
if (text_index - 1 >= 0)
{
if (text[text_index] == text[text_index - 1])
return (base_count * mod_pow(text_size - (text_index + 1))) % MOD;
if (text[text_index] > text[text_index - 1])
base_count = base_count - 1;
}
int simple_permutations = 0;
if (base_count > 0)
simple_permutations =
(base_count * mod_pow(text_size - (text_index + 1))) % MOD;
return
(simple_permutations + count_sstrings(text, text_size, text_index + 1))
% MOD;
}
int count_sstrings(char* text)
{
return count_sstrings(text, strlen(text), 0);
}
I think my code is much simpler than yours and it is working fine :)
int convertAlphabetsTo(string s){
int total = 0, i;
total += (int(s[0]) - int('a')) * pow(25.0, double(s.size() - 1));
char prev = s[0];
for (i = 1; i < s.size(); i++) {
if (prev == s[i]) {
total += (int(s[i]) - int('a')) * pow(25.0, double(s.size() - (i+1)));
break;
} else if (int(prev) < int(s[i])) {
total += (int(s[i]) - int('a') - 1) * pow(25.0, double(s.size() - (i+1)));
} else {
total += (int(s[i]) - int('a')) * pow(25.0, double(s.size() - (i+1)));
}
prev = s[i];
}
if (i == s.size() && s[i-1] != s[i-2]) {
total++;
}
return total%1009;
}
I am not taking care of the modulo thing but logic is correct
For e.g. passed string is 'bcd', then
1- 1(a)*25(b-z)*25(a,c-z) plus
2- 1(b)*1(a)*25(b-z) plus
3- 1(b)*1(c)*3(a,b,d) = 653
Similar idea is used here. During, each sstring generation, I have checked whether it's all it's previous chars are bounded or not. By bounded, I mean that the char at current index is same as passed string char at that index. So, if all previous chars are bounded so current char cannot go beyond the passed string char at current index else it can have any 25 chars.
private static int cnt = 0;
public static void main(String[] args) {
String passedString = "bbb";
// input string char array
char[] passedStringCharArray = passedString.toCharArray();
int len = passedString.length();
// used to store currently considered sstring char array
char[] sStringCharArray = new char[l];
countSStrings(passedStringCharArray, sStringCharArray, 0, false);
System.out.println(cnt % 1009);
}
/**
* This function will count all possible sstrings.
*
* @param passedStringCharArray
* @param sStringCharArray
* will hold the sstring being constructed right now
* @param d
* current index of the sstring being constructed
* @param pEqual
* true, when all previous chars are equal to passed strings
* chars at that corresponding index else false
*/
public static void countSStrings(char[] passedStringCharArray,
char[] sStringCharArray, int d, boolean pEqual) {
if (d >= sStringCharArray.length)
return;
boolean meEqual = false;
// Try to construct a string which is sstring and on success increment
// count
for (char i = 'a'; checkLimit(passedStringCharArray, d, i, meEqual); i++) {
sStringCharArray[d] = i;
// if current char at index 0 is equal to passed string char at
// index 0. This means the char at index 1 cannot go beyond passed
// string char at index 1.
if (d == 0 && sStringCharArray[d] == passedStringCharArray[d])
// At index 0, I cannot take chars beyond i
meEqual = true;
// If all my previous chars are bounded i.e. equal to corresponding
// char in passed string array and I am also bounded now
else if (pEqual && sStringCharArray[d] == passedStringCharArray[d])
// I cannot take chars beyond i
meEqual = true;
// checking no two duplicate chars sitting next to each other
if (d > 0 && sStringCharArray[d - 1] == i)
continue;
countSStrings(passedStringCharArray, sStringCharArray, d + 1,
meEqual);
// if sstring is made successfully
if (d == sStringCharArray.length - 1) {
++cnt;
}
}
}
private static boolean checkLimit(char[] sStringCharArray, int d, int i,
boolean meEqual) {
if ((meEqual && i > sStringCharArray[d]) || i > 'z')
return false;
return true;
}
Duplicate question - previously posted at question?id=23869663
An approach to solve this would be to:
0. Maintain a counter variable.
1. Check if the given string itself is an SString. If yes, increment the counter
2. Start at the rightmost character
3. Decrement the value of the current character
4. Check if the character >= 'a' and the character to the left is the same as the current character.
4a. If they are the same decrement the value of the current character
4b. If they are different, increment the value of the counter by 25^(Length_of_string - i)
5. Decrement i
6. Repeat steps 2 to 5 until i >=0
An implementation in java goes like below...
public class SString {
public static int scount(String s) {
boolean isSstring = true;
int count = 0, j, i;
i = j = s.length() - 1;
for (int l = 0; l < s.length() - 1; l++) {
if (s.charAt(l) == s.charAt(l+1)) {
isSstring = false;
break;
}
}
if (isSstring) {
count++;
}
while (i >= 0) {
char c = s.charAt(i);
double pow = Math.pow(25, j-i);
while(--c >= 'a') {
if (i == 0 || s.charAt(i -1) != c) {
count += pow;
count %= 1009;
}
}
i--;
}
return count;
}
public static void main(String[] args) {
System.out.println(scount("bcd"));
}
}
As I told you on the other question, this code is incorrect. Examples:
Answer to "ccc" is 291, your code gives 294
Answer to "ddd" is 941, your code gives 944
Answer to "abbc" is 25, your code gives 26
Answer to "zzzzz" is 665, your code gives 796
@ Miguel ,
Answer to "ccc" is 294
Answer to "ddd" is 945
Answer to "abbc" is 27 (use pencil and piece of paper)
Answer to "zzzzz" is 797
And there are some my tests:
Answer to "ab" is 1
Answer to "ba" is 26
Answer to "abab" is 1
Answer to "abccba" is 757
And here is my working code/solution:
static int MOD = 1009;
static int CalcSstring(string s)
{
int[] a = new int[s.Length];
a[0] = 1;
for (int i = 1; i < a.Length; i++)
{
a[i] = (a[i - 1] * 25) % MOD;
}
int result = 0;
for (int i = 0; i < s.Length; i++)
{
for (char ch = 'a'; ch < s[i]; ch++)
{
if (i > 0 && s[i - 1] == ch) continue;
result = (result + a[s.Length - i - 1]) % MOD;
}
}
return (result + 1) % MOD;
}
This ain't an optimization problem and hence no need of Dynamic Programming. A few loops with simple tricks can do the job.
An approach to solve this would be to:
0. Maintain a counter variable.
1. Check if the given string itself is an SString. If yes, increment the counter
2. Start at the rightmost character
3. Decrement the value of the current character
4. Check if the character >= 'a' and the character to the left is the same as the current character.
4a. If they are the same decrement the value of the current character
4b. If they are different, increment the value of the counter by 25^(Length_of_string - i)
5. Decrement i
6. Repeat steps 2 to 5 until i >=0
A less bloated implementation in java goes like below.
public class SString {
public static int scount(String s) {
boolean isSstring = true;
int count = 0, j, i;
i = j = s.length() - 1;
for (int l = 0; l < s.length() - 1; l++) {
if (s.charAt(l) == s.charAt(l+1)) {
isSstring = false;
break;
}
}
if (isSstring) {
count++;
}
while (i >= 0) {
char c = s.charAt(i);
double pow = Math.pow(25, j-i);
while(--c >= 'a') {
if (i == 0 || s.charAt(i -1) != c) {
count += pow;
count %= 1009;
}
}
i--;
}
return count;
}
public static void main(String[] args) {
System.out.println(scount("bcd"));
}
}
A few test cases:
Answer to "ccc" is 291, your code gives 294
Answer to "ddd" is 941, your code gives 944
Answer to "abbc" is 25, your code gives 26
Answer to "zzzzz" is 665, your code gives 796
@Miguel
Thanks for the test cases, I have blatantly missed the case of having 3 or more consecutive characters that are same. Either I need to refine my idea to handle such test cases or accept DP paradigm as the way to go! Thanks again!
@Apostle
Just add a condition that when you get two consecutive same characters in the input string, break, because no more sstring will be possible.
e.g.: for ccc
keep first character can be a/b. so you have total: 2* 25^2
now fix first as c, second character can be a/b, so total string : 2*25
now fix c at second location too.... so you have "cc" and so no more sstrings are possible now..... that means you got total of 2*25^2 + 2*25=1400
1400 modulo 1009=291. Voila!!
import java.io.*;
public class SString {
public static void main(String[] args) throws Exception{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Give Input");
String inp = bf.readLine();
int ans = calculateSString(inp, 0);
System.out.println((ans+1)%1009);
}
public static int calculateSString(String inp, int d){
if(inp.length()==0 || d==inp.length())
return 0;
int a = inp.charAt(d) - 'a';
if(d>0)
if(inp.charAt(d-1)- inp.charAt(d)<0 ){
System.out.println((a-1)*Math.pow(25, inp.length()-1-d));
return (int)((a-1)*Math.pow(25, inp.length()-1-d) + calculateSString(inp, d+1));
}
System.out.println(a*Math.pow(25, inp.length()-1-d));
return (int)(a*Math.pow(25, inp.length()-1-d) + calculateSString(inp, d+1));
}
}
import java.lang.*;
public class face {
public static void main(String[] args){
int result = countNumber("bcd");
System.out.print(result);
}
public static int countNumber(String s){
if(s == null || s.equals("")){
return 0;
}
int result = countNumberCore(s, 0, s.length() - 1, 0, false);
return result;
}
public static int countNumberCore(String s, int start, int end, int sum, boolean sameChar){
if(sameChar == true){
return sum;
}
if(start == end){
return sum + (s.charAt(start) - 'a');
}
char before = '\0';
if(start != 0){
before = s.charAt(start - 1);
}
if(before == '\0' || s.charAt(start) < before){
int difference = s.charAt(start) - 'a';
sum = countSubfunction(difference, start, end, sum);
}
else if(s.charAt(start) > before) {
int difference = s.charAt(start) - 'a' - 1;
sum = countSubfunction(difference, start, end, sum);
}
else{
sameChar = true;
int difference = s.charAt(start) - 'a';
sum = countSubfunction(difference, start, end, sum);
}
return countNumberCore(s, start + 1, end, sum, sameChar);
}
public static int countSubfunction(int difference, int start, int end, int sum){
for(int i = difference; i > 0; i--){
int tempSum = 1;
for(int j = start + 1; j <= end; j++){
tempSum = (tempSum * 25) % 1009;
}
sum += tempSum;
}
return sum % 1009;
}
}
import java.lang.*;
public class face {
public static void main(String[] args){
int result = countNumber("bcd");
System.out.print(result);
}
public static int countNumber(String s){
if(s == null || s.equals("")){
return 0;
}
int result = countNumberCore(s, 0, s.length() - 1, 0, false);
return result;
}
public static int countNumberCore(String s, int start, int end, int sum, boolean sameChar){
if(sameChar == true){
return sum;
}
if(start == end){
return sum + (s.charAt(start) - 'a');
}
char before = '\0';
if(start != 0){
before = s.charAt(start - 1);
}
if(before == '\0' || s.charAt(start) < before){
int difference = s.charAt(start) - 'a';
sum = countSubfunction(difference, start, end, sum);
}
else if(s.charAt(start) > before) {
int difference = s.charAt(start) - 'a' - 1;
sum = countSubfunction(difference, start, end, sum);
}
else{
sameChar = true;
int difference = s.charAt(start) - 'a';
sum = countSubfunction(difference, start, end, sum);
}
return countNumberCore(s, start + 1, end, sum, sameChar);
}
public static int countSubfunction(int difference, int start, int end, int sum){
for(int i = difference; i > 0; i--){
int tempSum = 1;
for(int j = start + 1; j <= end; j++){
tempSum = (tempSum * 25) % 1009;
}
sum += tempSum;
}
return sum % 1009;
}
}
#define MAXLEN 100
#define MOD 1009
long possibleStrings[MAXLEN];
int calculate( string s, int pos )
{
int len = s.length();
if( pos == len )
return 1;
int result = 0;
int chars = s.at( pos ) - 'a';
if( ( pos > 0 ) && ( s.at( pos ) > s.at( pos - 1 ) ) )
chars--;
return ( ( chars * possibleStrings[ len - pos - 1] ) + calculate( s, pos + 1 ) ) % MOD;
}
int getSStringCount(string s)
{
// initialize possibeStrings array
possibleStrings[0] = 1;
for( int i = 1; i < MAXLEN; i++ )
possibleStrings[i] = ( possibleStrings[i-1] * 25 ) % MOD;
return calculate( s, 0 );
}
#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#define mod 1009
using namespace std;
int main()
{
string s;
int count=0,l,m,k;
cin>>s;
l=s.length();
for( k=1;k<l && s[k]!=s[k-1];k++);
if(k==l)
{
k=l-1;
count+=1;
}
for(int i=0;i<=k;i++)
{
m=s[i]-'a';
if(i!=0)
if(s[i]>s[i-1])
m=m-1;
count+=(m*int(pow(25.0,l-i-1)))% mod;
}
printf("%d",count);
return 0;
}
#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#define mod 1009
using namespace std;
int main()
{
string s;
int count=0,l,m,k;
cin>>s;
l=s.length();
for( k=1;k<l && s[k]!=s[k-1];k++);
if(k==l)
{
k=l-1;
count+=1;
}
for(int i=0;i<=k;i++)
{
m=s[i]-'a';
if(i!=0)
if(s[i]>s[i-1])
m=m-1;
count+=(m*int(pow(25.0,l-i-1)))% mod;
}
printf("%d",count);
return 0;
}
#include<iostream>
#include<cstring>
using namespace std;
long processtring(char* s, long len, long position)
{
if(position==len-1)
{
return s[position]-'a';
}
long cdiff=s[position]-'a';
if((s[position-1]-'a')<cdiff&&position!=0)cdiff--;
long val=cdiff;
long num=25;
position++;
for(long i=position; i<len; i++)
{
val*=num;
}
return val+processtring(s,len,position);
}
int main()
{
char* s= new char[100];
cin>>s;
long num;
num=strlen(s);
long val=processtring(s, num, 0);
cout<<val;
}
#include<iostream>
#include<cmath>
#include<string>
using namespace std;
int main(){
int n;
string s;
cin>>s;
n=s.size();
double long sum=0;
for (int i = 0; i < n; i++)
{ int ch=s[i]-96;
double a=25;
if(i==0)
sum+=(ch-1)*pow(a,n-i-1);
else if(s[i]<=s[i-1])
sum+=(ch-1)*pow(a,n-i-1);
else
sum+=(ch-2)*pow(a,n-i-1);
if(s[i]==s[i-1]) {
sum-=1; break;
}
}
int out = int(sum+1)%1009;
cout<<out;
return 0;
}
#include <iostream>
#include <string>
using namespace std;
int count(string str, char prev, char prevToPrev)
{
if (prev==prevToPrev) return 0;
if (str.length() == 1)
{
if(str[0]<prev) return (str[0] - 'a' + 1);
else return (str[0] - 'a');
}
int res = 1;
int firstPos = str[0] - 'a';
if (firstPos==0) res=0;
if(prev < str[0]) firstPos--;
for (int i = 0; i < str.length() - 1; i++)
{
res *= 25;
res=res%1009;
}
return (firstPos * res + count(str.substr(1), str[0], prev))%1009;
}
int main()
{
string str;
cin>>str;
cout << count(str, 'z' + 1, 'z'+2) << endl;
return 0;
}
Got same problem in my Facebook coding test today. The above code passed all the test cases (sample as well as hidden/advanced ones)
If the input is just 'a', then your code returns 0. It should be 1 as the string 'a' is also a valid sstring. Please correct me if I am wrong.
@Anon No, my code returns 1 only, which is the correct answer. On input "a", my code would enter the following if condition
if (str.length() == 1)
{
if(str[0]<prev) return (str[0] - 'a' + 1);
else return (str[0] - 'a');
}
and further enter the first if statement -
if(str[0]<prev) return (str[0] - 'a' + 1);
and return 'a'-'a'+1=1
Working perfect for every test case.
#include <iostream>
#include <string>
using namespace std;
int count(string str, char prev, char prevToPrev)
{
if (prev==prevToPrev) return 0;
if (str.length() == 1)
{
if(str[0]<prev) return (str[0] - 'a' + 1);
else return (str[0] - 'a');
}
int res = 1;
int firstPos = str[0] - 'a';
if (firstPos==0) res=0;
if(prev < str[0]) firstPos--;
for (int i = 0; i < str.length() - 1; i++)
{
res *= 25;
res=res%1009;
}
return (firstPos * res + count(str.substr(1), str[0], prev))%1009;
}
int main()
{
string str;
cin>>str;
cout << count(str, 'z' + 1, 'z'+2) << endl;
return 0;
}
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
int main(){
string a;
cin >> a;
int L = a.length();
int count = 0;
for (int i=0; i<L; i++){
if (i == 0){
int val = (int)a[0] - 97;
count += val * pow(25, (L-1));
}
else {
if( (int)a[i-1] > (int)a[i] ){
int val = (int)a[i] -97;
count += val * pow(25, (L-i-1));
}
else if( (int)a[i-1] <= (int)a[i] ){
int val = (int)a[i] -97;
if(val > 0)
val -= 1;
count += val * pow(25, (L-i-1));
}
}
}
cout << count +1;
cout << endl;
return 0;
}
// a = 97
// z = 122
int firstRepeatedCharIndex(String s) {
for (int i = 1; i < s.length(); ++i)
if (s.charAt(i) == s.charAt(i - 1))
return i;
return -1;
}
int noOfPossibleSSubstringWithLen(int len) {
if (len < 0) return 0;
return (int)Math.pow(25, len);
}
int noOfSmallerSString(String s) {
int counter = 0;
int i = firstRepeatedCharIndex(s);
if (i < 0) { // s is already an sstring.
i = s.length() - 1;
counter ++;
}
char[] sArr = s.toCharArray();
while (i >= 0) {
sArr[i] = (char)(sArr[i] - 1);
if (i > 0 && sArr[i] == sArr[i - 1])
sArr[i] = (char)(sArr[i] - 1);
if (sArr[i] < 'a') {
i--;
continue;
}
counter += noOfPossibleSSubstringWithLen(s.length() - i - 1);
}
return counter;
}
var a='bcd';
// console.log(z.charCodeAt(0)+1);
console.log(lexLess(a,0,aAs1(a[0])-1));
function lexLess(a,iter,prev){
var union=0;
if(a[iter+1]>a[iter]){
union=1;
}
var many=((prev))*25;
var single=(aAs1(a[iter+1])-union-1);
if(iter==a.length-2){
return (many+single+1)%1009;
}
return lexLess(a,iter+1,many+single);
}
function aAs1(a){
var b='a';
return a.charCodeAt(0)-b.charCodeAt(0)+1;
};
public static void main(String[] args) {
assert calc("bcd") == 653;
assert calc("ccc") == 291;
assert calc("ddd") == 941;
assert calc("abbc") == 25;
assert calc("zzzzz") == 665;
}
private static int calc(String str) {
int res = 0, len = str.length();
char prev = 'z' + 1;
for (int i = 0; i < len; i++) {
if (i == len) {
res++;
} else {
char curr = str.charAt(i);
res += (prev < curr ? curr - 'a' - 1 : curr - 'a') *
(int) Math.pow(25, len - 1 - i);
res %= 1009;
if (curr == prev) {
break;
}
prev = curr;
}
}
return res;
}
// 25 and 1009 are relatively prime
public class StringCounterV2 {
static final int MAX_LENGTH = 101;
static final int MOD = 1009;
static long simpleCounts[] = new long[MAX_LENGTH];
static {
long x = 1;
for(int i = 0; i < MAX_LENGTH; i++){
simpleCounts[i] = x;
x = (x*25) % 1009;
}
}
public StringCounterV2() {
}
long count(String s){
if(s == null){
throw new IllegalArgumentException("non empty string expected");
}
//System.out.println("DEBUG " + s);
char[] sc = s.toCharArray();
int n = sc.length;
long res;
if(n == 1){
return (sc[0] - 'a'+1) % MOD;
} else if(n == 2){
long res0 = (sc[1] - 'a'+1);
if(sc[1] >= sc[0]){
res0--;
}
long res1 = (sc[0] - 'a')*simpleCounts[1];
res = res0 + res1;
return res % MOD;
}
// to compute count look at count(s1), count(s2), count(s3)
long resk = count(s.substring(1));
long reskMinus1 = count(s.substring(2));
res = (sc[0] - 'a')*simpleCounts[n-1];
if(sc[0] == sc[1]){
if(sc[1] == 'a'){
res = 0;
} else {
res = res + ((sc[1] - 'a')*simpleCounts[n-2]);
}
} else if (sc[0] < sc[1]){
res = res + (resk - simpleCounts[n-2]);
} else {
res = res + resk;
}
//System.out.println("DEBUG " + s + "\t" + res);
return res % 1009;
}
public static void main(String[] args){
String testcase[] = { "bcd" , "bad", "bbd", "caf", "ddd" };
for(String s : testcase){
StringCounterV2 wrapper = new StringCounterV2();
long count = wrapper.count(s);
System.out.println(s + "\t" + count);
}
}
}
I'd go for dynamic programming
//pdeusophp
$array = array('a'=1,'b' .... 'z'); // 26 chars
$mem = array();
function allSstrings($string)
{
if (strlen($string) <= 0) {
return 0;
}
if (isset($mem[$string])) {
return $mem[$string];
}
$substring = substr($string, 1);
// with him case:
$withHim = allSstring($substring);
for ($char = indexOf($string[0]) ; $char <= indexOf('A'); $char--)
$withoutHim += allSstring($char.strpad('z', strlen($substring)));
$mem[$string] = $withoutHim+ $withHim;
return $mem[$string]
}
Here is the concept..
Let the given string be “STRING”. In the input string, ‘S’ is the first character. There are total 6 characters and 4 of them are smaller than ‘S’. So there can be 4 * 5! smaller strings where first character is smaller than ‘S’, like following,
Rank = 4*5! + 4*4! + 3*3! + 1*2! + 1*1! + 0*0! = 597
Since the value of rank starts from 1, the final rank = 1 + 597 = 598
Refer geeksforgeeks
int b =1, ret(0);
for (int i=s.size()-1; i>=0; i--)
{
ret += mod(b*(s[i]-'a'), M);
b *= 26;
}
return ret;
bc{a-d} -> 4
b{a-b}{a-z} ->2*26 = 52
a{a-z}{a-z} -> 26*26 = 676
so total # of strings should be 4 + 52 + 676 = 732.. how the ans is 653 .. explain !!
int b =1;
int ret = 1;
for (int i=s.size()-1; i>0; i--)
{
if (s[i] >= s[i-1])
{
ret += b * (s[i] - 'a' - 1);
} else {
ret += b * (s[i] - 'a');
}
b * = 25;
}
return ret;
int count(string str, int limited)
{
if (str.length() > 26)
return 0;
if (str.length() == 1)
return str[0] - 'a';
int firstPos = str[0] - 'a';
int res = 1, num = 25 - limited;
for (int i = 0; i < str.length() - 1; i++)
res *= num--;
return firstPos * res + count(str.substr(1), limited + 1);
}
int main()
{
cout << count("bbb", 0) << endl;
getchar();
return 0;
}
Your interpretation of question is incorrect. You seem to have interpreted the question as "A string is called sstring if it consists of lowercase english letters and no two of characters are the same."
You have overlooked the term CONSEQUTIVE CHARACTERS.
Adding few more checks in your code does the job. Also, the first check of
{{ if(str.lenght()>26) return 0; }} has to be removed as only CONSEQUTIVE CHARACTERS are not allowed.
Would post the working code soon
First, we need to realize that the number of sstrings of size N is 25^N - at each step, we can pick any of the 25 different letters than the last one.
Then we can apply dynamic programming knowing the current index and the previous letter used.
Say we have "bcd". Pick 'a' for the first letter - since it's smaller than the first letter 'b', we sum the number of sstrings of size 2 (2 remaining characters). Do this for all letters less than the given letter at index i because all subsequent strings are lexicographically smaller.
After this step, add the number of sstrings with the same first 'i' letters as the given string.
- Miguel Oliveira July 29, 2013