## Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

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()));
}

}``````

Comment hidden because of low score. Click to expand.
0

looks like my sol will only work for cases like abcD or abCD or AbcD
but not aBcD ....hmmmm

Comment hidden because of low score. Click to expand.
0

This is a very inefficient algorithm.`

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

Upper case letters remain unchanged, and permute the lower case letters

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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()) {
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());
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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()));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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(){
print_permu(c,0,strlen(c));
cout<<"\ncount = "<<count<<endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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()) {
return generatedPermutations;
}

for (String str : currentPermutations) {

// simply add uppercase letters to the end
if (Character.isUpperCase(newChar)) {
continue;
}

// insert newChar at each index of str
for (int i = 0; i < str.length(); i++) {
if (Character.isLowerCase(str.charAt(i)))
}

// add the final permutation (with newChar at the end)
}

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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
AfCdEb
AfCbEd``````

Comment hidden because of low score. Click to expand.
0

Awesome code !! works perfectly

Comment hidden because of low score. Click to expand.
0
of 0 vote

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) {
}
}
return returnList;
}

public static ArrayList<String> permute(String str) {
char lastChar = str.charAt(0);
ArrayList<String> stringList = new ArrayList<String>();
String starterString = ""+lastChar;
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();
}
}
return returnList;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)

else
anag("", prefix);
}

public static void anag(String prefix, String string){
if(string.length() == 0)

else
for(int i = 0; i<string.length(); i++)
anag(prefix + string.charAt(i), string.substring(0,i) + string.substring(i+1));

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.