CareerCup

Pretty interesting question. The trick would be return from the recursion if idx of uppercase character in original string != idx of uppercase char in permutation generated so far

Here is the code

public static void generatePerm(String s) {
		 generatePermHelper(s, "", s);
	 }
	 
	 private static void generatePermHelper(String orig, String sofar, String rem) {
		 if (rem == null || rem.length() == 0) {
			 System.out.println(" Permutation is " + sofar);
		 }

		 
		 for (char c: rem.toCharArray()) {
			 int idx = rem.indexOf(c);
			 if (Character.isUpperCase(c)) {
				 sofar+=c;
				 if(sofar.indexOf(c)!=orig.indexOf(c)) {
					 return;
				 }
				 rem = String.valueOf(ArrayUtils.remove(rem.toCharArray(), idx));
				 generatePermHelper(orig, sofar, rem);
				 break;
			 }

			 generatePermHelper(orig, sofar+c, rem.substring(0,idx) + rem.substring(idx+1, rem.length()));
		 }

	 }

do you mean that the upper case letters remain unchanged or that they permute only among the positions of upper case letters?

Oh..may be we could generate permutations as usual like in regular recursive case and
just have this extra check:

if (Character.isUpperCase(c)) {
				 if(sofar.indexOf(c)!=orig.indexOf(c)) {
					 return;
				 }
                }

Assume there are no duplicates in the string.

import java.util.*;

public class Solution {
    public ArrayList<String> perm(String s) {
    	ArrayList<String> list = new ArrayList<String>(); 
    	helper(list, s, 0);
    	return list;
    }
    
    public void helper(ArrayList<String> list, String s, int start) {
    	if (start == s.length()) {
    		list.add(s);
    		return;
    	}
    	
    	if (Character.isUpperCase(s.charAt(start))) {
                // if the current char is uppercase, directly recur to the next char in order to preserve its position
    		helper(list, s, start+1);
    	} else {
    		for (int i = start; i < s.length(); ++i) {
    			if (Character.isUpperCase(s.charAt(i))) {
    				continue;
    			}
    			s = swap(s, start, i);
    			helper(list, s, i+1);
    			s = swap(s, i, start);
    		}
    	}
    }
    
    public String swap(String s, int i, int j) {
    	char[] array = s.toCharArray();
    	if (array[i] != array[j]) {
    		array[i] ^= array[j];
    		array[j] ^= array[i];
    		array[i] ^= array[j];
    	}
    	return new String(array);
    }
    
    public static void main(String[] args) {
    	String S = "aBBc";
    	Solution solution = new Solution();
    	System.out.println(solution.perm(S).toString());
    }
}

Since the capital letters remain unchanged, we can pick the positions of the low case letters and use stl's next_permutation on them. The others are unchanged.

void PrintAllLowerCasePermutations(const string& s) {
    int i;
    vector<int> pos;
    string lower;
    for (i = 0; i < s.size(); i++)
        if (islower(s[i])) {  // #include <cctype>
            pos.push_back(i);
            lower += s[i];
        }
    sort(lower.begin(), lower.end());
    do {
        for (i = 0; i < pos.end(); i++)
            s[pos[i]] = lower[i];
        cout << s << endl;
    } while(next_permutation(lower.begin(), lower.end()));
}

Hi, this is my solution hava a look

#include<iostream>
#include<cstring>
using namespace std;
int count;
// this program is a modified ver of printing all permutations
// we just need to increment index and j in the for loop whenever there is a upper case letter
void swap(int &a,int &b){
	int t =a;
	a = b;
	b =t;
	}
void print_permu(char a[],int index,int n){
	if(index==n){
	for(int i=0;i<n;i++)
	cout<<a[i];
	cout<<"\n";
	count++;
	}
	else{
	for(int j=index;j<n;j++){
	if(islower(a[j])&&islower(a[index])){
	swap(a[index],a[j]);
	print_permu(a,index+1,n);
	swap(a[index],a[j]);
	}
	if(isupper(a[index]))
	index++;
	}
	}
	}
int main(){
	char c[10] = "aDiTya";
	print_permu(c,0,strlen(c));
	cout<<"\ncount = "<<count<<endl; 
	return 0;
	}

This is what I came up with:

public static ArrayList<String> getPermutations(String srcStr) {
    	
    	ArrayList<String> currentPermutations = new ArrayList<String>();
    	char[] chars = srcStr.toCharArray();
    	
    	// generate permutations by adding one letter at a time
    	for (char ch : chars) {
    		currentPermutations = generatePermutations(currentPermutations, ch);
    	}
    	
    	return currentPermutations;
    }
    
    /**
     * Creates a new set for permutations with currentPermutations and the added character, newChar
     */
    private static ArrayList<String> generatePermutations(ArrayList<String> currentPermutations, char newChar) {
    	ArrayList<String> generatedPermutations = new ArrayList<String>();
    	
    	// no permutations? just use this letter as a start
    	if (currentPermutations.isEmpty()) {
    		generatedPermutations.add("" + newChar);
    		return generatedPermutations;
    	}
    	
    	for (String str : currentPermutations) {
    		
			// simply add uppercase letters to the end
			if (Character.isUpperCase(newChar)) {
				generatedPermutations.add(str + newChar);
				continue;
			}
			
    		// insert newChar at each index of str
    		for (int i = 0; i < str.length(); i++) {
    			if (Character.isLowerCase(str.charAt(i)))
    				generatedPermutations.add(insertChar(str, newChar, i));
    		}
    		
    		// add the final permutation (with newChar at the end)
    		generatedPermutations.add(str + newChar);    		
    	}
    	
		return generatedPermutations;    	
    }
    
    private static String insertChar(String str, char ch, int index) {
    	
    	char[] array = new char[str.length() + 1];
    	
    	for (int i = str.length() - 1, j = array.length - 1; i >= 0; i--) {
    		
    		char nextChar = str.charAt(i);
    		
    		// chars to the left of the insertion index move to the corresponding index
    		if (i < index)
    			array[i] = nextChar;
    		
    		// insertion char
    		else if (i == index) {
    			array[j] = nextChar;
    			array[i] = ch;
    			j = i;
    		}
    		
    		// if cap move to corresponding index
    		else if (Character.isUpperCase(nextChar)) {
    			array[i] = nextChar;
    		}
    		
    		// shift non-cap to the right
    		else {
	    		array[j] = nextChar;
	    		j = i;
    		}
    	}
    	
    	return new String(array);    
    }

I used the standard swapping and recursion permutation algorithm.
If you don't know that, First of all check how to calculate permutations.

#include <iostream>

using namespace std;

void avoidCapitalPermutation(string& str, int k, int n)
{
    if(k==n)
        cout << str << endl;
    
    if(isupper(str[k]))
    {
        avoidCapitalPermutation(str,k+1,n);
    }
    else
    {
        for(int i=k;i<=n;i++)
        {
            if(!isupper(str[i]))
            {
                swap(str[i],str[k]);
                avoidCapitalPermutation(str,k+1,n);
                swap(str[i],str[k]);
            }
        }
    }
    
}
int main()
{
    string str = "AbCdEf" ; 
    
    avoidCapitalPermutation(str,0,str.length()-1);
    
    return 0;
}


o/p 
AbCdEf
AbCfEd
AdCbEf
AdCfEb
AfCdEb
AfCbEd

First find all permutations then ignore the strings having uppercase permuted.
Performance can be improved

package teasers;

import java.util.ArrayList;

public class StringPermutationUpperNoChange {

	public static void main(String[] args) {
		String string ="IluVyoU";

		ArrayList<String> permutation = permute(string);
		permutation = checkStrings(permutation, string);

		for (String str:permutation) {
			System.out.println(str);
		}

		System.out.println(permutation.size());
	}
	public static ArrayList<String> checkStrings(ArrayList<String> stringList, String mainStr){
		ArrayList<String> returnList = new ArrayList<String>();
		for(String str:stringList){
			int flag = 0;
			for(int i=0; i<str.length();i++){
				if ((str.charAt(i)>=65 && str.charAt(i)<=90) && (str.charAt(i) != mainStr.charAt(i))) {
					flag = 1;
					break;
				}
			}
			if (flag==0) {
				returnList.add(str);
			}
		}
		return returnList;
	}

	public static ArrayList<String> permute(String str) {
		char lastChar = str.charAt(0);
		ArrayList<String> stringList = new ArrayList<String>();
		String starterString = ""+lastChar;
		stringList.add(starterString);
		for(int i=1 ; i<str.length() ;i++) {
			char ch = str.charAt(i);
			stringList = permuteStrings(stringList,ch);
		}
		return stringList;
	}
	public static ArrayList<String> permuteStrings(ArrayList<String> strList, char ch) {
		ArrayList<String> returnList = new ArrayList<String>();
		for(String str:strList) {
			for (int i=0; i<=str.length(); i++) {
				StringBuilder newStringBuilder = new StringBuilder(str);
				newStringBuilder.insert(i, ch);
				String newString = newStringBuilder.toString();
				returnList.add(newString);
			}
		}
		return returnList;
	}
}

import java.util.ArrayList;
public class Testing {
	static ArrayList<String> anags = new ArrayList<String>();
	public static void main(String[] args){
	permu("aAbDcA");	
	}

public static void permu(String str){
String lowercases = "";
String uppercases = "";
for(int i = 0; i<str.length(); i++)
	if(str.charAt(i) >='a' && str.charAt(i) <='z')
		lowercases += str.charAt(i);

	else
		uppercases += str.charAt(i);
		
anag(lowercases);

for(String alowercase: anags){
	String stree = str;
for(int i = 0; i < uppercases.length(); i++){
	int x = stree.indexOf(uppercases.charAt(i));
	alowercase = alowercase.substring(0,x) + uppercases.charAt(i) + alowercase.substring(x);
	stree = stree.replaceFirst(String.valueOf(uppercases.charAt(i)), " ");}

System.out.println(alowercase);
	}
}	
	
	public static void anag(String prefix){
		if(prefix.length()<=2)
			anags.add(prefix);
		
		else
			anag("", prefix);
	}
	
	public static void anag(String prefix, String string){
		if(string.length() == 0)
			anags.add(prefix);
		
		else
			for(int i = 0; i<string.length(); i++)
				anag(prefix + string.charAt(i), string.substring(0,i) + string.substring(i+1));
		
	}

}

This is a simple approach.

1. from the string extract all small case characters.
2. Remember there position in original string. (Rather remember Upper case position in original string)
3. Generate all permutation of lower case string.
4. For each permutation in list, insert Upper case characters to construct new string. New string will have length as original string.