Array & String

CCI

• is unique

• check permutation

• URLify

• Palindrome Permutation

• One away

• String compression

• Rotate matrix

• Zero matrix

• String rotation

• Flatten Array

• Largest Rectangle in Histogram

Is unique

Check If string letter is unique or not.

solution

A: Create empty hash table and store each letter and value as true.

B: Iterate twice and compare each letters if it does not allow additional buffer.

Code (solution A)

Check permutation

Take two strings, check If string is permutation of the other

solution

Code (Solution A)

URLify

Replace all spaces in a string with %20. Given integer describes how long the actual length of string is.

Input

"Mr John Smith ", 13

Output

"Mr%20John%20Smith"

Solution

1. Count the number of spaces during the first scan of the string.

2. Parse the string again from the end and for each character:

   • If a space is encountered, store “%20”.

   • Else, store the character as it is in the newly shifted location.

Palindrome Permutation

Given a string, write a function to check if it is a permutation of a palindrome.

Input

"Tact Coa"

Output

true

Solution

Code

One away

Given 2 strings, and compare them and check if they are one edit (remove, insert, replace one letter)

Replacement, insertion, removal

Input

pale, ple => true

pales, pale => true

pale, bale => true

pale, bae => false

Solution

String compression

Compress repeating characters and return compressed string if the length is shorter than original string. If it is longer than original one, return original one.

Input

"aaabbbcddddaaa"

Output

"a3b3c1d4a3"

solution

There is 2 solutions to solve this problem.

A. Iterate whole array first

B. Check compressed string is longer or not at first.

Code

Rotate matrix

Input

Output

Solution

Zero matrix

Input

Output

Solution

String rotation

Input

Output

Solution

Largest Rectangle in Histogram

Input

For example, given the array[-2,1,-3,4,-1,2,1,-5,4],

Output the contiguous subarray[4,-1,2,1]has the largest sum =6.

Solution

1) Create an empty stack.

2) Start from first bar, and do following for every bar ‘hist[i]’ where ‘i’ varies from 0 to n-1.
……a) If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack.
……b) If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).

3)If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.

https://www.geeksforgeeks.org/largest-rectangle-under-histogram/

Code

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

Input

For example, given the array[-2,1,-3,4,-1,2,1,-5,4],

Output the contiguous subarray[4,-1,2,1]has the largest sum =6.

Solution

Code

Generate All possible permutations string

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

Input

For example, given a string "ABC",

Output
"A", "B", "C", "AB", "AC", "BC", "ABC"

Solution

Code