610. Case Flips

MediumStringBacktrackingBit Manipulation3 hints
RPby Rohit Parihar

A sign painter has the string s made of letters and digits. For every letter in s the painter may choose to write it in upper case or in lower case; digits are always written as they are.

Return every different string the painter can produce. Each string must appear exactly once and the strings may be returned in any order. The count is 2^k where k is the number of letters in s, so aim for time proportional to that count times the length of the string.

Example 1

Input:
s = "k7"
Output:
["k7","K7"]
Explanation:

One letter gives two strings, k7 and K7.

Example 2

Input:
s = "305"
Output:
["305"]
Explanation:

There are no letters, so the only string is 305 itself.

Example 3

Input:
s = "aB"
Output:
["aB","ab","AB","Ab"]
Explanation:

Two letters give four strings: ab, aB, Ab and AB.

Constraints

  • 1 ≤ s.length ≤ 8
  • s contains only English letters (either case) and digits.

How this problem is judged

Answers
The outer list may be in any order. Everything inside each item must match exactly.

Expected complexity

Time
O(n * 2^n)
Space
O(n)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…