letter case permutation leetcode

DEV Community

Posted on Feb 16, 2021

Solution: Letter Case Permutation

This is part of a series of Leetcode solution explanations ( index ). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums .

Leetcode Problem #784 ( Medium ): Letter Case Permutation

Description:

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. You can return the output **in any order .

Constraints:

• S will be a string with length between 1 and 12 .
• S will consist only of letters or digits.

When a problem asks us to deal with permutations, one of the obvious approaches is via recursion as recursion will allow us to fire off our helper function down each branching possibility.

Recursion also naturally favors a DFS approach, which is also good because it ensures that our recursion stack never gets too deep.

Our recursive helper function ( dfs ) is actually quite simple. If we start with the input string ( S ) fully lowercased, then we just need to make sure that each version of dfs calls itself down two branches: one in which the current character is left unchanged, and a second in which the character has been uppercased, but only if the character is a letter.

Then, whenever we reach the end of S , we can add the permutation to our answer array ( ans ).

Implementation:

Javascript and Python deal with string copies faster than character arrays, so dfs will maintain a string ( res ) that it will build up as the function is called recursively.

Java deals with char arrays faster than it does strings, so we can pass a reference to a singular central char array ( chArr ) and modify it as we go. This also means that we have to remember to undo our toUpperCase after the second dfs is fired off so that later recursions reaching this character start with it in lower case.

C++ alone out of the four languages has mutable strings, so we can just pass a full copy of S down and modify each char individually, rather than having to build out a res .

Javascript Code:

Python Code:

Top comments (1)

Templates let you quickly answer FAQs or store snippets for re-use.

• Email [email protected]
• Location Kolkata, India
• Joined Jul 3, 2020

Here's another solution. We can also use a Bit-Masking approach to solve this problem.

Solution.java

Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment's permalink .

Hide child comments as well

For further actions, you may consider blocking this person and/or reporting abuse

Take Control of Your Crypto: Creating Your Wallet with JavaScript

Mr. G - Nov 9

🙌 7 Tips to Build Your GitHub Profile Like a PRO 🚀

Bap - Nov 16

Improving Code Quality in React with JavaScript Best Practices

Suraj Vishwakarma - Nov 30

Python Memory Management Best Practices

TelemetryHub - Nov 8

Once suspended, seanpgallivan will not be able to comment or publish posts until their suspension is removed.

Once unsuspended, seanpgallivan will be able to comment and publish posts again.

Once unpublished, all posts by seanpgallivan will become hidden and only accessible to themselves.

If seanpgallivan is not suspended, they can still re-publish their posts from their dashboard.

Once unpublished, this post will become invisible to the public and only accessible to seanpgallivan.

They can still re-publish the post if they are not suspended.

Thanks for keeping DEV Community safe. Here is what you can do to flag seanpgallivan:

seanpgallivan consistently posts content that violates DEV Community's code of conduct because it is harassing, offensive or spammy.

Unflagging seanpgallivan will restore default visibility to their posts.

We're a place where coders share, stay up-to-date and grow their careers.

784. Letter Case Permutation

• Time: $O(2^n)$
• Space: $O(2^n)$

Similar Problems

Detect squares, minimum interval to include each query, merge triplets to form target triplet, hand of straights, distinct subsequences, min cost climbing stairs, swim in rising water, network delay time, min cost to connect all points, redundant connection, walls and gates, k closest points to origin, kth largest element in a stream, count good nodes in binary tree, binary tree right side view, number of connected components in an undirected graph, non overlapping intervals, lowest common ancestor of a binary search tree, graph valid tree, find minimum in rotated sorted array, encode and decode strings, house robber ii, subtree of another tree, counting bits, reverse bits, meeting rooms, word ladder ii, wiggle sort ii, valid phone numbers, letter case permutation.

Problem Statement

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

Input: S = “r2q” Output: [“r2q”, “R2q”, “r2Q”, “R2Q”]. Input: S = “678” Output: [“678”]

• S will be a string with length between 1 and 12.
• S will consist only of letters or digits.

We don’t have to take care of digits as they can’t help to find more pernutations. We only have letters with us now. Suppose a string have L letters in it. The number of possible permutation will 2 L .

This can be represented by bitmask bits.

For Example: we have g5h, we can represent all the possible permutations as g5h = 00, g5H = 01, G7h = 10, G7H = 11. Digits given in the input string are not included in bitmask.

According the possible bitmask, find out all the permutations, taking one bitmask at a time.

Implementation

Complexity analysis.

• Time Complexity: O(2 n *n).
• Space Complexity: O(2 n *n).

Privacy Policy

Terms & Conditions

Data Structures

Linked Lists

Data Structures & Algorithms

System Design

Company Wise Interview Questions

Interview topics.

Blind 75 Practice Problems With Solutions

Backtracking

Greedy Algorithms

Divide & Conquer

Modified Binary Search

Dynamic Programming

Google Interview Questions

Amazon Interview Questions

Adobe Interview Questions

Microsoft Interview Questions

Oracle Interview Questions

Uber Interview Questions

LinkedIn Interview Questions

Flipkart Interview Questions

Facebook Interview Questions

Goldman Sachs Interview Questions

Huawei Interview Questions

Top 100 Leetcode Practice Problems In Java