Let us consider the string in problem as S and the string that we generate as T.
What my solution does it:
Solve(1,S.size()):
Ans=0
1)If the first and last character of S and T are same,Ans+=Solve(2,s.size()-1)
2)If the first and last character of T are greater than S, then we can place any charcters from [2,S.size()-1].
3)If first character of T =first character of S,but last character of T is > last character of S,then we have to make sure that T[2,S.size()-2]>=S[2,S.size()-2]
4)If first character of T > first character of S,but last character of T is = last character of S,then we have to make sure that substring T[S.size()-2,2]>=S[S.size()-2,2]
Base Conditions: Solve(x,y) if x<y return 0
Solve(x,y) if x==y return ('Z'-S[x])
Here A[x,y] denotes substring of A from index x to y inclusive.
