CareerCup

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

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

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

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

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

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

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