CODEWITHSUNDEEP
javaalgorithm
Learner
Learner

Reputation: 21425

Minimum number of rotations needed to get original string

I have two strings, I want to know the minimum number of rotation/reversal of any substring to get the original string.

Example:

The two strings are:

abcdef
abdcfe

In above second string, the substring dc can be rotated to get abcdfe. Then next fe is rotated to get abcdef. So minimum rotations is 2. If a solution is not possible then I need to get -1.

To solve this I thought of getting all permutations of input string so I can decide where there is a possible result or to return -1. But I see this is not the correct approach as there is no way I can find the minimum rotations.

What is the approach to solve this problem.

Upvotes: 0

Views: 933

Answers (2)

libik
libik

Reputation: 23049

One way to solve it (not sure if effective enough though):

  1. Generate all possible substrings
  2. Do the rotation/reversing of all these substrings
  3. If solution is found - fine. If not, repeat the process for each single substring.

You can imagine it as directed tree-like graph, where initially there is your string in root, then all possible operations you can do are edges and in the nodes there are transformed strings. You are searching through it Breadth-first.

For example like this:

const reverse = str => Array.from(str).reverse().join('');

function subreverse(str, from, to) {
  const before = str.substring(0, from);
  const reversed = reverse(str.substring(from, to+1));
  const end = str.substring(to+1);
  
  return `${before}${reversed}${end}`;
}

// generates all possible substring-reverse transformation from given string
function findNewStrings(original) {
  const strLen = original.length;
  const newStrings = [];
  for (let i=1; i < strLen; i++) {
    for (let j=0; j < strLen - i; j++){
      newStrings.push(subreverse(original, j, j+i));
    }
  }
  
  return newStrings;
}

function findRotations(original, transformed) {
  let solution = undefined;
  let stack = [];
  let newStack = [];
  let iterations = 0;
  // using stack for BFS-like alghoritm
  stack.push({str: original, rotations: 0, history: original});
  
  // iterations is just to ensure that in case of some bug it will not end in endless loop
  while (!solution && iterations < 10) {
    iterations++;
    stack.forEach(item => {
      const newStrings = findNewStrings(item.str);
      newStrings.forEach(str => newStack.push(
      {str, rotations: item.rotations+1, history: `${item.history}->${str}`}));
    })
  
    solution = newStack.find(item => item.str === transformed);
    stack = newStack;
  }
  
  return solution;
}

console.log(findRotations('abcdef', 'abcdfe'));
console.log(findRotations('abcdef', 'abdcfe'));
console.log(findRotations('abcdefgh', 'ghabdcfe'));

Upvotes: 1

Prune
Prune

Reputation: 77850

First, the feasibility check is trivial: sort both strings and check whether they're equal.

Break the problem into subproblems: look for substrings with the same letters, bounded by letters in the correct position. In your case, you would break this into three: ab (done), cd/dc, and ef/fe. If found, solve each of these individually.

Your eventual solution will involve recursively searching the solution space. Start thinking about that now:

  • Identify each move that can move a letter to its desired position.
  • For each move in that list, make the move; recur with the remaining problem.

Note that the length of the string is an upper bound for any solution path.

That should get you moving. Note that you can apply heuristics to identify likely paths. For instance, compute the displacement of each letter (how far you have to move it). If you have a preponderance of similar values, that suggests a rotation. If you have negative values on one side and positive on the other, that suggests a reversal.

That should get you moving.

Upvotes: 0

Related Questions