title: Find Possible Original String From the Shuffled String
body: <p>I have a problem. Here is the description.</p>
  
  <blockquote>
    <p>Distance between 2 strings is the sum of absolute difference between
    the letters at same positions (e.g. difference("ab","cd") = 
    abs('a'-'c')+abs('b'-'d') = 4). There is a string <strong>orig</strong>. Then, the
    letters of <strong>orig</strong> is shuffled. Then, you can replace <strong>only one</strong>
    letter from the string with its next or previous letter in alphabet or
    do nothing (do not replace any letter). Let name the new string
    <strong>st</strong>. Let <strong>X</strong> is distance between <strong>st</strong> and <strong>orig</strong>. Given <strong>st</strong>.</p>
    
    <p>My problem is, given <strong>st</strong>, I need to generete for every distance
    <strong>X</strong> (where <strong>X</strong> = distance(orig, st), number of possible string <strong>orig</strong> from given string <strong>st</strong>.</p>
    
    <p>for more clear explanation: I need to generate the number of possible
    string orig that can transformed to st that have distance(orig, st)
    equal to <strong>X</strong> (where 0 &le; x &le; 250).</p>
    
    <p>constraint:</p>
    
    <ul>
    <li>'b' &le; st<sub>i</sub> &le; 'y' </li>
    <li>1 &le; |st| &le; 10</li>
    <li>0 &le; X &le; 250</li>
    </ul>
  </blockquote>
  
  <p>I've tried to use dynamic programming with bitmasking, but it seems to slow for the problem (the complexity is arround O(2<sup>|st|</sup> * |st| * |X|)). Is there any better algorithm or data structure that suit to solve this problem? Any hint or opinion is very appreciated. Thank you :D</p>
  
  <p>*let me know if there are unclear explanations :D</p>