The Forward And Backward Shift String Problem

We have a simple problem, we are given a string e.g. “abcd” and we have to check if the new strings formed by forward shift and backward shift are the same or not. 

 There is a reason I chose this problem. There are few basic concepts that you need to know to solve this type of problem in any language. The question in general is a very easy once you know about those concepts. As usual, we will try to solve this question with the most basic programming skills and later on in another article will cover more efficient ways to tackle such kinds of problems.

So, first to solve this problem we need to figure out two terms in the context of this question,

  1. Forward Shift - Moving each char forward in the string in a circular manner
  2. Backward Shift - Moving each char backward in the string in a circular manner.

Refer to the example mentioned below,

The Forward And Backward Shift String Problem

Now, there is one more concept you should be aware of before you jump into this question. I am gonna solve this problem using a data type - “StringBuilder”

Why you ask, well our normal string data types are immutable in nature, which means that they can’t be changed after creation and for my basic solution I need something with which I can repetitively make amendments. That’s why we would be using a more flexible String Builder data type. For detailed information about string builders, refer to the blog mentioned in the references. Now let’s solve this problem.

Approach

We would simply create two variables, fstring and bstring. For forward string, we will push the last char from string first and then iterate the remaining elements and add them to one of our variable fstring, similarly, for backward string we will iterate from the second character element from s and add the elements to bstring and add the first element at the end of the loop. We will compare the two stringBuilders by converting them into string objects. This is because,

Two different string builders cannot be compared as they reference different objects**so they would not be equal.

Code

using System;
using System.Text;
public class Program {
    public static void Main() {
        string s = "bbbbbbbb";
        int len = s.Length;
        //Forward Shift -> dabc
        char c1 = s[len - 1];
        StringBuilder fstring = new StringBuilder();
        fstring.Append(c1);
        for (int i = 0; i < len - 1; i++) {
            fstring.Append(s[i]);
        }
        //Backward Shift -> bcda
        char c2 = s[0];
        StringBuilder bstring = new StringBuilder();
        for (int i = 1; i < len; i++) {
            bstring.Append(s[i]);
        }
        bstring.Append(c2);
        Console.WriteLine("Input String = {0}", s);
        if (bstring.ToString() == fstring.ToString()) {
            Console.WriteLine("SAME STRING");
        } else {
            Console.WriteLine("NOT SAME");
        }
    }
}

Output

Input String = bbbbbbbb

Input String = abcd

The Forward And Backward Shift String Problem

References

  1. Immutability of Strings
  2. String Builder Detailed