String replacement with characters from Map to generate all possible combinations

String replacement with characters from Map to generate all possible combinations Given a hashmap M which is a mapping of characters to arrays of replacement characters, and an input string S, return an array of all possible combinations of S (where any character in S can be substituted with one of its substitutes in M, if it exists). What is the time complexity? What is the space complexity? Can you optimize either? Example input: M = { f: [F, 4], b: [B, 8] } S = fab Expected output: [FaB, Fa8, 4aB, 4a8]