## Facebook Interview Question for Software Engineer / Developers Front-end Software Engineers

Country: India

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

``````const int MAX = 102, MOD = 1009;
int dp[MAX][27], len, sstrings[MAX];
char str[MAX];

int solve(int i, int prev) {
if (i == len)
return dp[i][prev] = 1;
if (dp[i][prev] == -1) {
dp[i][prev] = 0;
for (int c = 'a'; c < (int)str[i]; c++)
if (c-'a' != prev)
dp[i][prev] += sstrings[len-i-1];
if (prev != str[i]-'a')
dp[i][prev] += solve(i+1, str[i]-'a');
dp[i][prev] %= MOD;
}
return dp[i][prev];
}
int main() {
scanf("%s", str);
len = strlen(str);
sstrings[0] = 1;
for (int i = 1; i <= len; i++)	// sstrings[i] = 25^i % MOD
sstrings[i] = (sstrings[i-1] * 25) % MOD;
memset(dp, -1, sizeof dp);	// -1 meaning not calculated yet
printf("%d\n", solve(0, 26));	// 26 is a non-existing letter before the start
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

I could not understand why will you pick 'a' as it is not present in input string 'bcd' ?

Comment hidden because of low score. Click to expand.
1
of 1 vote

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"

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@Zuzu, that code is incorrect. See the other post with test cases

Comment hidden because of low score. Click to expand.
0

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];``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@Miguel Oliveira Can you explain what exactly dp[i][j] means? Thanks a lot!

Comment hidden because of low score. Click to expand.
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++;
}
}``````

I am not taking care of the modulo thing but logic is correct

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 2 vote

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"));
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

As I told you on the other question, this code is incorrect. Examples:

Comment hidden because of low score. Click to expand.
0

@ Miguel ,
Answer to "abbc" is 27 (use pencil and piece of paper)

And there are some my tests:

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

@Zuzu, it's easy to check by hand or even by brute force that the answer to "abbc" is 25. It's the strings "abab", "abac", "abad".. "abaz".

Comment hidden because of low score. Click to expand.
0
of 0 vote

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"));
}
}``````

Comment hidden because of low score. Click to expand.
0

A few test cases:

Comment hidden because of low score. Click to expand.
0

@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!

Comment hidden because of low score. Click to expand.
0

@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!!

Comment hidden because of low score. Click to expand.
0

@Miguel Oliveira
The answer to zzzzz is 142? Shouldn't it be (25^5 + 25^4) that is 665?

Comment hidden because of low score. Click to expand.
0

Yes, it's 665, i prefer to put it as 26*25^4. My code also gives 665, I made a mistake putting the 142.

i edited the post

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.*;
public class SString {

public static void main(String[] args) throws Exception{
System.out.println("Give Input");
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));

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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 );
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

Add modulus operator in main :
val=val%1009;

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
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)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

LOL. Just look at the code above your answer by sc.shobhit (me). Uncannny similarity :\

It feels good that my code proved to be useful for you but atleast don't repost exactly same version.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// 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);
}
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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--)

\$mem[\$string] =  \$withoutHim+ \$withHim;

return \$mem[\$string]
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

Did you test this? This doesn't even answer the sample "bcd" -> 653, your code gives 731

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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 !!

Comment hidden because of low score. Click to expand.
0

"A string is called sstring if it consists of lowercase english letters and no two of its consecutive characters are the same."

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;

Comment hidden because of low score. Click to expand.
0

This is wrong. For example, for "bbb" your code returns 1 and the answer is 650 (a[a-z][a-z])

Comment hidden because of low score. Click to expand.
-1
of 3 vote

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

Comment hidden because of low score. Click to expand.
0

I got the 653 for "bcd".

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.