CareerCup

i think this question frequently asked in ms
void swap(char *s,int i,intj);
{
char temp;
temp=s[i];
s[i]=s[j];
s[j]=temp;

}

void Permutaions(char str[],int i)
{
int n;
int k;
n=strlen(str);
if(i==n)
{
puts(str);
return;
}
for(k=i;k<=n-1;k++)
{
swap(str,i,k);
Permutaion(str,i+1);
swap(str,i,k);
}
}

public class PermuteString {

	public static void main(String[] args) {
		permute("4aaabbb");
	}
	
	public static void permute(String s) {
		if(s == null) return;
		StringBuilder sb = new StringBuilder(s);
		System.out.println(sb.toString());
		while(true) {
			int i;
			for(i = sb.length()-1; i > 0; i--) {
				if(sb.charAt(i-1) < sb.charAt(i)) break;
			}
			i--;
			if(i == -1 ) break;
			int j;
			for(j = sb.length()-1; j > i; j--) {
				if(sb.charAt(i) < sb.charAt(j)) break;
			}
			swap(sb, i, j);
			reverse(sb, i+1, sb.length() - 1);
			
			System.out.println(sb.toString());
		}
	}
	private static void swap(StringBuilder sb, int i, int j) {
		char c;
		
		c = sb.charAt(i);
		sb.setCharAt(i, sb.charAt(j));
		sb.setCharAt(j, c);
	}
	private static void reverse(StringBuilder sb, int i, int j) {
		for(int k = 0; k < (j-i+1)/2; k++) {
			swap(sb,i+k,j-k);
		}
	}
}

I think in your algo if you pass "zpa" it will print nothing.

If you want to deal with same character, you can use next_permutation in STL.
Below is the implementation of next_permutation

template <typename BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last)
{
   if(first == last)
       return false;
   BidirectionalIterator i = first;
   ++i;
   //if only one element
   if(i == last) 
     return false;
   i = last;
   --i;
   for(;;)
   {
      BidirectionalIterator j = i;
      --i;
      if(*i < *j) 
      {
         BidirectionalIterator k = last;
         while(!(*i < *--k))
            ;
         std::iter_swap(i,k);
         std::reverse(j,last);
         return true;
      }
      if(i == first)
      {
           std::reverse(first, last);
           return false;
       }
    }
}

#include <stdio.h>
#include <string.h>

static void permuteStringImp(char *s, int pos, int len);
static void swap(char *s, int i, int j);

void permuteString(char *s, int len)
{
        if(s == NULL || s[0] == '\0' || len <= 0)
                return;

        permuteStringImp(s, 0, len);
}

static void permuteStringImp(char *s, int pos, int len)
{
        int i;
        if(pos >= len)
        {
                printf("%s\n", s);
                return;
        }

        for(i = pos; i < len; i++)
        {
                swap(s, pos, i);
                permuteStringImp(s, pos+1, len);
                swap(s, pos, i);
        }
}

static void swap(char *s, int i, int j)
{
        char temp;
        temp = s[i];
        s[i] = s[j];
        s[j] = temp;
}

void permute(string rem, string prefix, vector<string>& permutations)
{
	string::iterator it = rem.begin();
	if(it == rem.end())
		permutations.push_back(prefix);
	while(it != rem.end())
	{
		string newrem(rem.begin(), it);
		newrem += string(it + 1, rem.end());
		permute(newrem, prefix + *it, permutations);
		it++;
	}
}