CareerCup

This is a De Bruijn sequence problem.
See https://en.wikipedia.org/wiki/De_Bruijn_sequence#Algorithm

public String digits(Integer n, String input){
Integer k=0;
String digits=null;
if(input!=null&&!input.isEmpty()) { k = input.length();}
if((k>n||k==n)&&input.matches("[0-9]+")){
digits=input.substring((k-n), input.length()); }
else{ digits="not a valid password"; }
return digits;
}

public String digits(Integer n, String input){
Integer k=0;
String digits=null;
if(input!=null&&!input.isEmpty()) {
k = input.length();
}
if((k>n||k==n)&&input.matches("[0-9]+")){
digits=input.substring((k-n), input.length());
}
else{
digits="not a valid password";
}
return digits;
}

Please tell us your approach

n-actual password, input-how many ever characters you enter
my code checks if the entered password is not null and it contains all digits only, and, trims to last n-digits that is meant for password and returns the same.

Can we do it with pattern matching algorithm?

Solved by finding a Hamiltonian path of size K^N

unordered_set<string> visited;

    bool crackSafeHelp(const string &start,string &res,int k,int pow){
        if(visited.size() == pow){
            return true;
        }
        
        string newNode = start.substr(1);
        
        for(int i = 0; i < k; ++i){
            string digit = to_string(i);
            string temp = newNode + digit;
            
            if(visited.find(temp) == visited.end()){
                res += digit;
                visited.insert(temp);
                if(crackSafeHelp(temp,res,k,pow)){
                    return true;
                }
                
                visited.erase(temp);
                res.pop_back();
            }
        }
        
        return false;
    }
    
    string crackSafe(int n, int k) {
        int power = pow(k,n);
        string start(n,'0');
        string res(n,'0');
        visited.insert(start);
        crackSafeHelp(start,res,k,power);
        return res;
    }

it is exactly same as leetcode 753.. copy and paste?

slightly modified leetcode solution so that it works on both num and alphabet.

class Solution(object):
    # n: length
    # k: alphabet
    def DeBruijn(self, n, k):
        seen = set()
        answer = []
        try:
            alphabet = list(map(str, range(k)))
        except(ValueError, TypeError):
            alphabet = k
        def dfs(node):
            for x in alphabet:
                neighbor = node + x 
                if neighbor not in seen:
                    seen.add(neighbor) 
                    dfs(neighbor[1:]) 
                    answer.append(x) 
        dfs(alphabet[0] * (n-1))
        # print(seen)
        return "".join(answer) + alphabet[0] * (n-1)