Baekjoon Algorithm | Problem 1759: Making Password

Tags:

Source

https://www.acmicpc.net/problem/1759

Problem

Solve Baekjoon Online Judge problem 1759, Making Password.

Input

Follow the input format and constraints given in the original problem statement.

Output

Print the answer required by the problem.

Sample Input 1

4 6 a t c i s w

Sample Output 1

acis acit aciw acst acsw actw aist aisw aitw astw cist cisw citw istw

Algorithm Classification

  • Math
  • Brute Force
  • Combinatorics
  • Backtracking

Solution

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int L;
    static int C;
    static char[] chars;
    static char[] keys;

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer input = new StringTokenizer(br.readLine(), " ");
            L = Integer.parseInt(input.nextToken());
            C = Integer.parseInt(input.nextToken());

            input = new StringTokenizer(br.readLine(), " ");

            chars = new char[C];
            for (int i = 0; i < C; i++) {
                chars[i] = input.nextToken().charAt(0);
            }
        }

        Arrays.sort(chars);

        keys = new char[L];

        cypherText(0, 0);
    }

    private static void cypherText(int start, int index) {
        if (index == L) {
            int mo = 0;
            int ja = 0;

            for (char x : keys) {
                if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') {
                    mo++;
                } else {
                    ja++;
                }
            }

            if (mo >= 1 && ja >= 2) {
                System.out.println(keys);
            }

            return;
        }

        for (int i = start; i < C; i++) {
            keys[index] = chars[i];
            cypherText(i + 1, index + 1);
        }
    }
}