Print permutations of string replaced with digits

Given a string, print the variation of string as shown below
Input String: ‘hat’

• Replace one character with numeric one(‘1’): ‘1at‘, ‘h1t‘, ‘ha1‘
• Replace two characters with ‘1’ each: ‘11t‘, ‘h11‘, ‘1a1‘
• Replace three characters with ‘1’ each: ‘111‘

In all the strings above, wherever the numeric characters are consecutive, add them. So ’11t’ will become ‘2t’, Similarly ‘111’ will become ‘3’. So the final output will be

hat ha1 h1t h2 1at 1a1 2t 3

Solution:

This looks like a permutation problem in the first place, but actually it is not. Because the arrangement of characters is not changing. For ex. ‘h’ will always be before ‘a’ and ‘t’.

replacing characters with digit is not a big challenge. The core challenge is when the digits gets added and a single digit will be printed in place of two digits.

We need some helper functions for this.  First we need a function to check whether a character is a digit or not. Second, we need a function to convert string to Number.

The logic is that for each character in the string, there will be two outputs

• When that character appears in the output.
• When ‘1’ appears in place of that character (if previous character is also a digit then we increment that number, else append ‘1’)

Code:

Below is the code for the above logic.

#include <iostream>
#include <cstring>
using namespace std;
/**
 * Function to check whether a character is a digit or not.
 */
bool isDigit(char ch)
{
    return (ch >='0' && ch<='9');
}
/**
 * Given a number 'num', the function reverse the digits of that number and return
 * that new number.
 */
int reverseNum(int num)
{
    int reverse = 0;
    while(num != 0)
    {
        reverse = reverse*10 + num%10;
        num = num/10;
    }
    return reverse;
}
/**
 * This function extract the digits in string str from position start to end and
 * conver it to number and return that number.
 */
int strToNum(char* str, int start, int end)
{
    int num = 0;
    for(int i=start; i<end;i++)
    {
        int digit = str[i] - '0';
        num = num*10 + digit;
    }
    return num;
}
/**
 * Will try to add '1' at pos in the string 'str'. If character at position pos-1 is also a digit
 * then it will increment the digit at pos-1 rather than appending '1'.
 * Returns the final position (position of last character) in the string.
 *
 * If str is 'abc12' then output 'abc13'.
 * If str is 'abc' then output 'abc1'.
 * If str is 'abc1' then output 'abc2'.
 * If str is '111' then output '3'.
 */
int addOneAtEnd(char* str, int pos)
{
    // Case when the last character is not a digit
    if(pos==0 || !isDigit(str[pos-1]))
    {
        str[pos]='1';
        return pos+1;
    }
    int i=pos-1;
    while(i>=0 && isDigit(str[i]))
        i--;
    // i points to one place before the first digit. So Increment it
    i++;
    int number = strToNum(str, i, pos);
    // At this point we have a number that need to be appended in the string starting
    number++;
    // Reversing the number to append it at the end of the string.
    int reverse = reverseNum(number);
    // Adding number at the end of string
    pos = i;
    while(reverse != 0)
    {
        int d = reverse%10;
        reverse = reverse/10;
        str[pos] = d + '0';
    }
    str[pos+1]='\0';
    return pos+1;
}
void printPatternRecursive(char* inStr, char* outStr, int posIn, int posOut)
{
    if(inStr[posIn] == '\0')
    {
        outStr[posOut] = '\0';
        std::cout<<outStr<<" ";
        return;
    }
    // Adding character of input string
    outStr[posOut] = inStr[posIn];
    printPatternRecursive(inStr, outStr, (posIn+1), (posOut+1));
    // Adding '1'
    int pos = addOneAtEnd(outStr, posOut);
    printPatternRecursive(inStr, outStr, (posIn+1), (pos));
}
void printPatterns(char* str)
{
    // Output Array where individual string will be stored
    int size = strlen(str)+1;
    char *strOut = new char[size];
    // Current Position in Input Array
    int curPosIn = 0;
    // Current position in Output Array
    int curPosOut = 0;
    printPatternRecursive(str, strOut, curPosIn, curPosOut);
}
int main()
{
    char origStr[] = "hat";
    printPatterns(origStr);
    return 0;
}

The above code takes O(n) time.