CareerCup

The logic is with atmost 2 special character(let assume it to be as k and k=0,1,2). Consider a spl[]={'1','2','3','4','5','6','7','8','9','0','5','#','&','!'} size=14

k=0:
test

k=1:
_test
t_est
te_st
tes_t
test_

We can work out these combinations from i=0 to 5(array size) and fill it from the spl[]

k=2:
case 1: joined (2 blanks together__)
__test
t__est
te__st
tes__t
test__

We can work out these combinations from (i=0 to 6(word test +2 blanks)) and (j=i+1 and j<6) and fill it from the spl[]

case 2: varied

set 1: i=0 is fixed and j=i+2 to 6
_t_est
_t_est
_te_st
_tes_t
_test_

set 2: i=1 is fixed and j=i+2 to 6
t_e_st
t_es_t
t_est_

set 3: i=2 is fixed and j=i+2 to 6
te_s_t
te_st_

set 4: i=3 is fixed and j=i+2 to 6
tes_t_


We can work out these combinations from (i=0 to 3) and (j=i+2 to j<6) and fill it from the spl[]


Filling with spl array:

k=0: N/A

k=1: fill index from0 to 13(size is 14)

k=2: fill index1 from0 to 13(size is 14)
fill index2 from0 to 13(size is 14)

public void printSpecialCharsCombo(char charArray[], String word){
  if(charArray.length == 0)
           return 

 for(int j = 0; j < word.length;j++){
     String combination = word.substring(0, i) + "charArray[0]" + word.substring(i, word.length()-1);
     System.out.println(combination);
      String charArrayToString =  charArray.toString();
       charArrayToString = charArrayToString.subString(1, charrArrayToString.length() -1);
       char[] splicedCharArray = charArrayToString.toCharArray();

     printSpecialCharsCombo(newCharArray, combination);
 
  }
}

Time Complexity: O(2^n)

could you please explain the logic?

looks like a high school combinatrics problem rather than an Amazon one. total number of possible combinations will be C(n,1)*C(m+1,1)+C(n,2)*C(m+1,2) where n = number of special characters and m= length of the string. use the same logic to find all the possible combinations. converting the given string to a linked list rather than an array would be much more efficient for insertion and string manipulationpurpose.

Using multiple for loops we can try following logic too :

let s is the given string or word, ch[] is character array of special characters
s1 will be the string first part, while s2 will be the string second part.

output will be
s,ch[]s,sch[],ch[]ch[]s,sch[]ch[], s1ch[]s2, s1ch[]ch[]s2.

We can print multiple combinations like this:
print(s)
for i=0 to n, print(ch[i]s);
ffor i=0 to n, print(sch[i]);
for i=0 to n,for j=0 to n, print(ch[i]ch[j]s);
ffor i=0 to n, for j=0 to n, print(sch[i]ch[j]);
for i=0 to n,for j=0 to n,for k=0 to s.length() print (s[i]ch[k]s[j]);
for i=0 to n, for j=0 to n,for k=0 to s.length(),for l=0 to l.length() print(s[i]ch[k]ch[l]s[j]);

The best way here I think is to try string permutation.

The following code steal the ideas from balance parenthesis generator, whose basic idea is : if you can put an open, put it; if you have less close, put it; if you have used all, then you are done.

char *cs = "0123456789%#&!";
char *used="00000000000000";

void permute(char *str, int count, char *buf, int pos)
{
	// if you have used all the special char
	// concat the str and print it out;
	if(count == 0){
		strcpy(buf+pos, str);
		printf("%s,", buf);
		return;
	}
	
	// if you can put a special char 
	// put it in the current position of buf
	int i = 0;
	while(used[i] == '1') continue;
	buf[pos] = cs[i];
	used[i] = '1';
	permute(str, count-1, buf, pos + 1);

	// also, you can put a char from str
	// instead
	used[i] = '0';
	buf[pos] = str[0];
	permute(str+1, count, buf, pos + 1);
}

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

#define ARRAY_SIZE( array ) sizeof( array ) / sizeof( array[0] )

//
// Insert a string into any existing string at position pos
//
void insertChar(char *source, int pos, char *newchar) {

	if (strlen(source) < pos) {
		return;
	}

	int destLength = strlen(source) + 1 + strlen(newchar);
	char* destination = (char*)malloc(sizeof(char) * destLength);

	strncpy_s(destination, destLength, source, pos);
	strncat_s(destination, destLength, newchar, strlen(newchar));
	strncat_s(destination, destLength, source + pos, strlen(source)-pos);
	
	int newSourceLength = destLength;
	realloc(source, sizeof(char) * newSourceLength );
	memcpy_s(source, newSourceLength, destination, destLength);
	free(destination);

	return;
}

//Given a word and special characters print all the combinations of that word along with atmost 2 special characters
//Word - test
//special characters 0-9,%,#,&,!
//Eg: test, test1, test2, te3st, te1!st, test#%, 12test, !te5st, t0est&, etc. etc.

int printCombo( char *word) {

	char* specialChar[] = {"0","1","2","3","4" ,"5" ,"6" ,"7" ,"8" ,"9", "%", "#", "&", "!" };
	int wordLength = strlen(word);
	printf("==================== Printing COMBO ===================== \n");
	int newWordLength1symbol = wordLength + 1; 
	int newWordLength2symbol = wordLength + 2; 
	for (int symbolIndex = 0; symbolIndex < ARRAY_SIZE(specialChar) ; symbolIndex ++) {
		for (int position = 0; position <= wordLength; position++) {
			char* newWord = (char*) malloc(sizeof(char) * newWordLength1symbol);
			memcpy_s(newWord, newWordLength1symbol, word, strlen(word) + 1);
			insertChar(newWord, position, specialChar[symbolIndex]);
			printf("%s \t", newWord);
			for (int nextSymbolIndex = symbolIndex + 1; nextSymbolIndex < ARRAY_SIZE(specialChar) ; nextSymbolIndex ++) {
				for (int position = 0; position <= wordLength; position++) {
					char* newWord2Symbols = (char*) malloc(sizeof(char) * newWordLength2symbol);
					memcpy_s(newWord2Symbols, newWordLength2symbol, newWord, strlen(newWord) + 1);
					insertChar(newWord2Symbols, position, specialChar[nextSymbolIndex]);
					printf("%s \t", newWord2Symbols);
					free(newWord2Symbols);
				}
			}
			free(newWord);

		}
	}

	printf("\n ==========================================================\n");
	return 0;
}

int main() {
	printf("PRINT COMBO  \n");
	char* myString = "test";
	printf("The word is   %s \n ", myString);
	printCombo(myString);
	getchar();
}

Try my java solution:
public class WordMix {

static final char[] specialChars =
{ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '%', '#', '&', '!' };

/**
* @param args
*/
public static void main(String[] args) {
final String word = "test";
char[] result = new char[word.length() + 2];
solve(result, word.toCharArray(), 0, 0, 0);
}

static void solve(char[] result, char[] input, int top, int ind, int spChars) {
if (ind == input.length && spChars >= 0) {
System.out.println(new String(result, 0, top));
}
if (ind < input.length) {
result[top] = input[ind];
solve(result, input, top + 1, ind + 1, spChars);
}
if (spChars < 2) {
for (int i = 0; i < specialChars.length; i++) {
result[top] = specialChars[i];
solve(result, input, top + 1, ind, spChars + 1);
}
}
}
}

- pick up 0 from special characters, just print test;
- pick up 1 from special characters, combine it with word "test", and then combine one more special character. such as: let each combination which contains '0' and "test" combines one more special character '1'.

refer to below algorithm which is a little ugly in C. please comments......

void combineWord(char word[], char spec, char spec2)
{

int i;
char *cOut=NULL;
int n=strlen(word);
cOut = (char *)malloc(n+1);

for(i=0; i<n+1; i++)
{
if(i==0)
{
memcpy(&cOut[i+1], &word[i], n);
}else if(i==n)
{
memcpy(&cOut[0], &word[0], n);
}else
{
memcpy(&cOut[0], &word[0], i);
memcpy(&cOut[i+1], &word[i], n-i);
}
cOut[i]=spec;
printf("%s, ", cOut);

if(n<5)
{
combineWord(cOut, spec2, '\0');
}
}
printf("\n\r");
}

main()
{
char *cWord="test";
char *cSpec="0123456789%#&!";
char cOutPut[6]={0};
int iWordLen=strlen(cWord);
int iSpecLen=strlen(cSpec);

printf("%s, ", cWord);

int i, j;
for(i=0; i<iSpecLen-1; i++)
{
for(j=i+1; j<iSpecLen; j++)
{
combineWord(cWord, cSpec[i], cSpec[j]);
}
}
}

For any value of special characters in between (not just 2):

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void PlaceBetween(int n,int index,string a,string punc,List<string> output)
        {
            if (index == n)
            {
                return;
            }
            for (int i = 0; i < punc.Length; i++)
            {
                for (int j = 0; j <= a.Length; j++)
                {
                    if (!a.Contains(punc[i]))
                    {
                        string pre = a.Substring(0, j);
                        string post = a.Substring(j);
                        string newstring = pre + punc[i] + post;
                        output.Add(newstring);
                        PlaceBetween(n, index + 1, newstring, punc, output);
                    }
                }
            }
        }
        static void Main(string[] args)
        {
            int n=2;
            string a = "test";
            string punc = "0123456789%#&!";
            List<string> output = new List<string>();
            output.Add(a);
            PlaceBetween(n,0,a,punc,output);
        }
    }
}