I have been given a string T comprised of only 's','t','u','v' as characters . I want to find numbers of strings with length |T| which differs at atmost n position from T. Also each such string must not have same character at three different locations which are separated by same distance . My approach is using dynamic programming method such that dp[i][j][k] denotes number of such strings of length i , differing at j position while ending at kth character , where k=s,t,u,v .
if(k is same at ith character of T)
dp[i][j][k]=dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2]-(strings which are extra due to k added at ith location and violates condition of same separated distance )
but i know this is wrong ?
eg for this is suppose T ='sstt' and we have to find strings which differ at most 2 locations then strings which do not have same character at three different location separated by same distance are 'tstt', 'ssts' and etc