{"id":792,"date":"2020-06-11T08:29:12","date_gmt":"2020-06-11T08:29:12","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=792"},"modified":"2022-03-21T12:28:00","modified_gmt":"2022-03-21T12:28:00","slug":"character-combine","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/character-combine\/","title":{"rendered":"Character Combine"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Recursion<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given two characters C1<\/code>, C2<\/code> and an integer K<\/code>, print all the possible
\nK<\/code> length combinations of both the characters. Print the combinations lexicographically.<\/p>\n

NOTE<\/strong>:<\/p>\n

\n
    \n
  1. \n

    Characters can be repeated. <\/p>\n<\/li>\n

  2. \n

    Consecutive C2<\/code> characters are not allowed.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n<\/blockquote>\n

    <\/strong><\/u><\/a><\/p>\n

    For Example:<\/h4>\n

    \"\"<\/p>\n

    Can we use Recursion<\/code> here ?<\/em><\/strong><\/p>\n

    \n

    Yes, here we need to find combinations that satisfy the given conditions. Recursion<\/code> is a good choice to find all such combinations.<\/p>\n<\/blockquote>\n

    SOLVING APPROACH:<\/h3>\n
    \n
      \n
    1. Initialize an empty string str<\/code> and recursively keep adding characters C1<\/code> and C2<\/code> to it based on the following cases :
      \n
      \n
        \n
      • \n

        If str<\/code> is empty, you can add either C1<\/code> or C2<\/code>. <\/p>\n<\/li>\n

      • \n

        If str<\/code> is not empty, check if the last character is C2<\/code> or not. If it is C2<\/code>, you can add only C1<\/code> as consecutive C2's<\/code> are not allowed. If it is C1<\/code>, you can add either C1<\/code> or C2<\/code>. <\/p>\n<\/li>\n

      • \n

        Keep adding characters till length of str<\/code> becomes equal to K<\/code> and then print str<\/code>.<\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n<\/li>\n<\/ol>\n<\/blockquote>\n

        STATE SPACE TREE:<\/h3>\n

        \"\"<\/p>\n

        SOLUTIONS:<\/h3>\n\t\t\t\t\t\t