Re-arrange a string into a { consonant, vowel, consonant, vowel ... } sequence

I was prompted to give someone advice about the following problem:

Given a string with equal amount of vowels and consonants, re-arrange it so that it follows the sequence { consonant, vowel, consonant, vowel, ... }

For Example given "abed" modify it to be "bade". The order of the vowels and consonants must be the same, "dabe" nor "beda" are acceptable answers.

It was a "first year" type question, no std::string, no strlen, no copying the characters somewhere else, ...

Anyway, I came up with this. Basically, while iterating through the string, if the character isn't what we're looking for, move another pointer forward until it finds one. Once found, store it and then shift each character one to the right to make space for the character that we want:

#include 

bool isVowel( const char ch )
{
  return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}

void rearange( char *str )
{
  bool on_consonant = true;

  while ( *str )
  {
    bool is_vowel = isVowel( *str );

    if ( ( on_consonant && is_vowel ) || ( !on_consonant && !is_vowel ) )
    {
      char *ptr = str + 1; // we don't get here with a valid string
      while ( isVowel( *ptr ) == is_vowel )
        ++ptr;

      // ptr now points to the first type we are looking for
      char swap = *ptr;

      // move each character up the line
      while ( ptr != str )
      {
        *ptr = *( ptr - 1 );
        --ptr;
      }

      *str = swap;

    }
    ++str;
    on_consonant = !on_consonant;
  }

}

int main( int argc, char *argv[] )
{
  if ( argc != 2 )
  {
    std::cout << "please enter a valid string as an argument\n";
    return 0;
  }

  std::cout << argv[1] << '\n';
  rearange( argv[1] );
  std::cout << argv[1] << '\n';

  return 0;
}

I realize that the \$O\$ notation of this isn't very good, we are going to be going back and forth across this string many times. I really couldn't think of a better way to do it with the constraints that were given. I was trying to d

You have tagged this question with algorithm, and I like algorithm problems. In the spirit of the original question, the solution should not be using any additional space, which means your char vector suggestion at the end is not really relevant. I would agree with your analysis, that the problem is reduced to \$O(n)\$ by storing the vowels and consonants in different vectors, and then merging them again... but that relies on an \$O(n)\$ space complexity too.

I think the solution that the original problem (with no additional storage) is looking for, is a three-pointer option.... a 3-point turn, to make a bad pun.

Consider the following algorithm, which contains three pointers. Each pointer advances sequentially from the beginning to the end of the char array. There is a 'rotate' operation that makes a temp copy of the last char in an array slice, it then shifts all previous chars forward one, and then inserts what was the last char, at the front.

The three pointers consitute an \$O(n)\$ sequence through the data, and the rotate is another \$O(n)\$ operation, but worst-case is n/2, and the worst case will reduce significantly as the pointers advance, and the gap tightens up.... Technically, though, the time complexity combined worst case is \$O(n^2)\$ though.

So, in pseudocode:

• set three pointers all to the first char

• vowel pointer will, when set, point to the next available vowel - initialize to 0

• consonant pointer will, when set, point to the next abailable consonant - initialize to 0

• insert pointer - initialize to 0

• loop while the insert pointer is valid

• advance the vowel pointer to the next vowel (inclusive of the current char)

• advance the consonant pointer to the next consonant (inclusive of the current char)

• rotate the consonant to the insert pointer.

• if the consonant was after the next vowel, indicate that the vowel has advanced 1 char

• advance the insert pointer

• rotate the vowel to the insert point.

• if the vowel was after the consonant, indicate the consonant advanced 1 char

• advance the insert pointer

• advance the vowel pointer

• advance the consonant pointer

So, working off this, and using beginner-level C++ (I am a Java person), I put together the following functions:

bool isVowel( const char ch )
{
  return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}

void rotate(char *from, char *to)
{
    char c = *to;

    while (--to >= from)
    {
        *(to + 1) = *to;
    }
    *from = c;
}

void rearange( char *str )
{

  char *vowel, *consonant;
  vowel = str;
  consonant = str;

  while ( *str )
  {
    while (*consonant && isVowel(*consonant))
    {
        consonant++;
    }
    while (*vowel && !isVowel(*vowel))
    {
        vowel++;
    }

    rotate (str, consonant);
    if (consonant > vowel)
    {
        vowel++;
    }
    str++;

    rotate (str, vowel);
    if (vowel > consonant)
    {
        consonant++;
    }
    str++;

    consonant++;
    vowel++;
  }

}

This is in an Ideone here;

The advantages here are that the logic for the boolean on_consonant is removed. Additionally, the pointers only ever advance, and never have to be re-located (if you ignore the rotate...)

StackExchange Code Review Q#64121, answer score: 5