6
\$\begingroup\$

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 <iostream>

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 do it in linear time, but the problem is that you never know how far forward the correct character will be and it is possible to overwrite data that hasn't even been looked at.

I offered another solution, which I do believe is linear \$( 2 * n )\$, using no constraints.

void rearange( std::string& str )
{
  std::vector< char > vowels( str.length() / 2 );
  std::vector< char > consonents( str.length() / 2 );

  size_t v_idx = 0;
  size_t c_idx = 0;

  for ( char ch : str )
    isVowel( ch ) ? vowels[ v_idx++ ] = ch : consonents[ c_idx++ ] = ch ;

  str.clear();
  for ( size_t i = 0; i < consonents.size(); ++i )
  {
    str += consonents[i];
    str += vowels[i];
  }
}

Am I correct that this is a linear operation? Are there any other ideas that could speed this up? ( Though, I'm not too worried about it, it currently takes twice as long to even make the random string ).

\$\endgroup\$
  • \$\begingroup\$ A linear solution. Have two pointer. One pointing at vowels the other at constants. Init both to first value in the string. One will point to the first character in the string. If it is the wrong type swap the content pointed at by the pointers. Move the start point one update the two pointers. \$\endgroup\$ – Martin York Sep 29 '14 at 4:04
  • \$\begingroup\$ @LokiAstari - I believe the swap is not possible, in the event that you have aeixyz, the first consonant will be x, and swapping that with a will result in the vowel order being off .... A 'rotate' is needed, not just a swap. \$\endgroup\$ – rolfl Sep 29 '14 at 4:13
  • \$\begingroup\$ For the input "abed", is "bade" the only valid solution, or is, for example, "deba" also valid? \$\endgroup\$ – mjolka Sep 29 '14 at 4:40
  • \$\begingroup\$ Just "bade", they have to stay in order. \$\endgroup\$ – Carl Sep 29 '14 at 4:52
  • \$\begingroup\$ @rolfl: Works fine. See below. \$\endgroup\$ – Martin York Sep 29 '14 at 5:20
5
\$\begingroup\$

You have tagged this question with , 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...)

\$\endgroup\$
4
\$\begingroup\$

Puzzels. Love them.

This is a O(n) problem. But just to make it more fun, we can also do it in O(1) space (no extra space).

#include <functional>
#include <iostream>

Your test for is a vowel is fine but you miss the upper case letters. You can make it a single look-up (assuming ASCII-like coding in 8-bit chars):

bool isVowel(unsigned char x)
{
    static char vowelTest[] = {
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, // A E I O
                0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // U
                0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, // a e i o
                0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // u
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

    return vowelTest[x];
}
bool isConst(unsigned char x)
{
    return !isVowel(x);
}

To make things easier, I am going to use an auxiliary function. This steps along the array until we find the type of character we want.

char* findNext(char* data, std::function<bool(unsigned char)> test)
{
    while(test(*data))
    {   ++data;
    }
    return data;
}

The re-arrange function.

We need to maintain two cursors (one for vowels and one for constants). We will keep these in an array (which means we can programmatically switch between them). We keep track of how far we are through the string in str.

void rearange(char* str)
{
    char*   data[2]     = { findNext(str, isVowel), findNext(str, isConst)};
    bool    vowelNow    = false;

    // While we are still in the sting.
    while(*str)
    {
        // If we have the correct value under the correct cursor.
        if (data[vowelNow] == str)
        {
            // Then just move the cursor.
            data[vowelNow]       = findNext(data[vowelNow]+1, isConst);
        }
        else
        {
            // The characters are not in the correct place.
            std::swap(*data[0], *data[1]);

            // Now both pointers point at the wrong type of characters.
            // So move them both forward.
            data[0]     = findNext(data[0]+1, isVowel);
            data[1]     = findNext(data[1]+1, isConst);
        }

        // Move forward the start point.
        // And switch the type of letter we are looking for.
        ++str;
        vowelNow    = !vowelNow;
    }
}

int main()
{
    char val[] = "abed";
    std::cout << val << "\n";
    rearange(val);
    std::cout << val << "\n";
}

And the test run:
http://ideone.com/AouDPU

\$\endgroup\$
  • 1
    \$\begingroup\$ I love puzzles too, found this one in a beginner thread, "hey, not bad". The order of the characters must stay the same: "aedf" becomes "dafe", which this answer does not solve. I wasn't clear about that. \$\endgroup\$ – Carl Sep 29 '14 at 5:13
  • \$\begingroup\$ @Carl: The term for that is Stable. \$\endgroup\$ – Martin York Sep 29 '14 at 5:22
  • \$\begingroup\$ If you need it to be stable and O(n) then you need to use more memory still O(n) but you need to allocate a replacement block to hold results. \$\endgroup\$ – Martin York Sep 29 '14 at 17:49
  • \$\begingroup\$ I believe there is a stable \$O(n)\$-time, \$O(1)\$ auxiliary space algorithm. Partition the string into all vowels followed by all consonants, which can be done in-place in \$O(n)\$-time, then interleave the two halves. \$\endgroup\$ – mjolka Sep 29 '14 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.