Given an array, how do you rotate it counter clockwise around a given input index position? i.e. If the input array was [1, 2, 3, 4, 5, 6, 7, 8], the result of rotation around index 3 (that has the element 4) in the counter clockwise direction would be [5, 6, 7, 8, 1, 2, 3, 4]. The sequence of transformations the array goes through as each of the elements until the given index rotates would be:

1 2 3 4 5 6 7 8            --> input array
2 3 4 5 6 7 8 1            --> 1 has rotated away to the end of the array
3 4 5 6 7 8 1 2            --> 2 has rotated away following 1
4 5 6 7 8 1 2 3            --> now, it's 3's turn
5 6 7 8 1 2 3 4            --> the element at index 3 (i.e. 4) around which we
                               wanted to rotate has also completed.

We can use the algorithm we developed to reverse a sub-array, in order to achieve this rotation. The idea is simple:

1. First, reverse the sub-array consisting of elements from the beginning of the array until the pivot (around which we want to rotate the array) in place
2. Now, rotate the remaining sub-array alone (i.e. from the pivot until the end of the array
3. Complete it by reversing the entire array once

1 2 3 4 5 6 7 8            --> input array
4 3 2 1 5 6 7 8            --> step-1 first sub-array reversed
4 3 2 1 8 7 6 5            --> step-2 second sub-array reversed
5 6 7 8 1 2 3 4            --> step-3 rotation of the entire array 

An implementation would look like:

void rotate_arr_ccw(int arr[], int size, int pivot)
{
  reverse_arr(arr, 0, pivot);
  reverse_arr(arr, pivot+1, size-1);
  reverse_arr(arr, 0, size-1);
}

A string is an isogram if no character in it appears more than once.

Let us write a simple algorithm to identify if a given input string is an isogram. For simplicity let us consider only strings that have small characters and no spaces or special characters i.e. - only characters from a to z.

In our previous post, we learnt how to keep track of characters that appear in a string as we traverse the input string. We use the same idea here, just this time we simplify it to be 26 characters (a to z) instead of 256.

1. We traverse the input string and maintain a counter for each of the occurences in the string. Note that we subtract ‘a’ from the ASCII value as our strings contain only a to z and we want our index 0 to correspond to a. The intention of this simplification was precisely to learn how to modify our algorithm for such specific use cases.
2. We traverse the counter array (which is essentially a mapping seen: character -> count to see if any of the characters appeared more than once (i.e. their count mapping is greater than 1).

#define MAX_CHARS 26
bool isogram(std::string s)
{
  int seen[MAX_CHARS] = {0};
  int slen = s.length();
  bool res = true;

  // (1)
  for (int i = 0; i < slen; i++)
    seen[s[i] - 'a']++;

  // (2)
  for (int i = 0; i < 26; i++)
  {
    if (seen[i] > 1)
    {
      res = false;
      break;
    }
  }
  return res;
}

Today, let us see how we can figure out if two given input strings are isomorphic using a time-efficient algorithm.

Given two strings s1 and s2 if there is a unique mapping from each of the characters of one to the other, then they are isomorphic

For example, anna and naan are isomorphic with the mapping a -> n and n -> a. Similarly aab and xxy are isomorphic with the mapping a -> x and b -> y, while aab and xyz are not isomorphic. However, anna and naa are not isomorphic as there is no direct mapping for the last a of anna (a hint that the strings should be of equal length for them to be isomorphic).

An approach is to traverse one of the strings and mark the occurence of the character in the string. The nice thing about character strings is that there are only 256 ASCII characters and hence we can have a character array of size 256 to mark the occurence of characters in a string. Along with marking the occurence, we need to store the mapping of this character to the corresponding (array index) character of the second string.

1. During the very first encounter of a character, say the first a (index 0) in anna, we check if the corresponding index in the other string naan has already been visited.
2. We visit it (i.e. remember it in some algorithmic way).
3. We store the mapping of this visit (i.e. a -> n).
4. If we encounter a character again, say the last a in anna, we check for the mapping to see if the corresponding index in the second string is as per our expectations (i.e. obeys the mapping).

The way we maintain the mapping is through an array map and we also maintain whether we already visited a particular character using an array visited. Since we need two additional arrays of size 256 each, there is some cost we pay for this space. However, we traverse the input array only once and so it would be O(n) time algorithm. These four steps are noted in the code fragment below for easier reference.

#define MAX_CHARS 256
bool isomorphic(std::string s1, std::string s2)
{
  bool visited[MAX_CHARS] = { false };
  int map[MAX_CHARS];

  // initialize map
  for (int i = 0; i < MAX_CHARS; i++)
    map[i] = -1;

  // check if both strings are of equal length
  int slen1 = s1.length();
  int slen2 = s2.length();
  if (slen1 != slen2)
    return false;

  // traverse s1 and update marked and visited
  for (int i = 0; i < slen1; i++)
  {
    // (1) first occurence
    if (map[s1[i]] == -1) 
    {
      // check if corresponding s2 char is visited
      if (visited[s2[i]] == true)
        return false;

      // (2) update visited
      visited[s2[i]] = true;                          

      // (3) store mapping
      map[s1[i]] = s2[i];                             
    }
    // (4) not the first occurence? check the mapping
    else if (map[s1[i]] != s2[i]) 
      return false;
  }
  return true;
}

In an earlier post, we saw how to reverse a given input array. But, it reversed the entire array. What if we want to pick a fragment of the input array and reverse only that?

Let us assume we are given the start and end indices - the window that we want to reverse. It is very similar to our previous approach, except that we need to be careful computing the indices to iterate on.

void reverse_arr(int arr[], int start, int end)
{
  int mid = (start + ((end - start)/2));
  for (int i = start; i <= mid; i++)
    swap(&arr[i], &arr[end - (i - start)]);
}

There is an interesting story about computation of mid-point given two window boundaries. At first glance, it would seem tempting to write it as (start + end) / 2 but it is safer (and more correct) to write it as start + ((end - start) / 2).

In yesterday’s post we saw how to check if two given strings are rotations of each other. Today, we will add one other restriction to the problem and try to solve it. What if the algorithm needs to check if the two input strings are rotations of each other by a fixed length n which is also provided as an input to the function? For example, anna and naan are rotations of each other by 2 as we need to make two rotations (each rotation moves only 1 character) to get from one string to the other and similarly one cannot be obtained from the other by rotation of just 1.

We use the same algorithm as before, but this time we will be careful to store the index position (when we search for one of the strings in the concatenation) and match it against the input n.

bool str_rot_by_n(std::string s1, std::string s2, int n)
{
  if (s1.length() != s2.length())
    return false;
  int index;
  std::string s = s1 + s1;
  index = s.find(s2);
  if (index == std::string::npos)
    return false;
  else
  {
    if (index == n || (index == (s1.length() - n)))
      return true;
    else
      return false;
  }
}

Again, we have to check if the lengths of the input strings are the same. Without this check, we migth deduce that ello can be obtained from hello by rotating through 1 character position.