## Is subsequence

Given a string s and a string t, check if s is subsequence of t. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not). For example:

```Input:
s="ace" ,t= "abcde"
Output:
True

Input:
s="aec" t="abcde"
Output:
False
```

## Approach

This problem looks similar to edit distance problem which can be solved using dynamic programming. The only difference is only deletions are allowed in this problem.

Recursive approach

What happens if we take a character at index i from string s and a character at index from string t? There are two possibilities: either these characters are equal or they are not equal. If the characters are equal, then we found the corresponding character in the target string, so we have to look for a remaining substring from index i+1 in s in substring in t from index j+1
What if the characters are not equal? In that case, we keep looking in substring of t from index j+1, but the index of s does not change, it remains at i, because we have not found the match for this character yet in the target string.

Implementation note: `s.substring(1)` actually get the substring of the string from the second character to the last character and achieves the increase in the indices as mentioned above.

``` private boolean isSubsequenceUtil(String s, String t){

if(s.length() == 0) return true;

if(t.length() == 0) return false;

return (s.charAt(0) == t.charAt(0)
&& isSubsequenceUtil(s.substring(1), t.substring(1)))
|| isSubsequenceUtil(s, t.substring(1));

}
```

If you run the above code in Leetcode, it will give you Time Limit Exceeded error, that becomes obvious when we draw the execution tree of the function, we will notice that we are solving the same problem multiple times.

Top down approach

The first thing we should do it to avoid solving the subproblem, again and again, that can be achieved using memorization. We introduce a caching place to store if we have solved the problem already and if yes, what was the result. If we already have solved the problem, we will just use the result and not solve the problem again. Below is the memorization code.

``` private boolean isSubsequenceUtil(String s, String t, boolean[][] isKnown,
boolean[][] value,
int sIndex, int tIndex){

if(s.length() == sIndex) return true;

if(t.length() == tIndex) return false;

if(isKnown[sIndex][tIndex]){
return value[sIndex][tIndex];
}

value[sIndex][tIndex] = (s.charAt(sIndex) == t.charAt(tIndex)
&& isSubsequenceUtil(s, t, isKnown, value,
sIndex+1, tIndex+1))
|| isSubsequenceUtil(s, t, isKnown, value, sIndex, tIndex+1);

isKnown[sIndex][tIndex] = true;

return value[sIndex][tIndex];
}
```

This code passes all the test cases at Leetcode. This approach is called a top-down approach in dynamic programming, where we start with the top, keep solving smaller problems until we find a solution for the original problem.

Bottom up approach

Since the optimal solution to the subproblems leads to optimal solution to the original problem, we can apply another approach called the bottom-up approach. In this approach, we start from the smallest possible problem and build our solution upwards.

What is the smallest problem possible in this case? If string s is empty and target string t is not empty, s is definitely a subsequence although an empty one.
So, if I create a two dimensional array where rows represent the number of characters in t and column represent number of characters in s, then I can initialize the first column (which represents zero length of the source string) as

```for(int i=0; i<=t.length(); i++){
dp[i][0] = true;
}
```

Other way around, what if string t is empty and string s is not empty, then there is no way possible string s can be subsequence of string t, this can be filled in the table as follows:

```for(int i=0; i<=t.length(); i++){
dp[0][i] = false;
}
```

What if we move up a bit, let’s say we have i characters in string t and j characters in string s. We compare the i-th character with j-th character and see if there are equal?
If they are equal and if string t with i-1 characters already has string s with j-1 characters as subsequence, then we can mark that string t with i characters has string s with j characters as subsequence too.

If the characters are not equal, then either string s with j characters should already be subsequence in i-1 characters of string t, or it cannot be a subsequence in i characters either.

```dp[i][j]= t[i] == s[j] && dp[i-1][j-1]
dp[i][j]= dp[i-1][j]
```

If we go through each character in both string. One implementation note, i and j represent the length of strings and not the index, that is why we compare characters at index i-1 and j-1 when solving for dp[i][j]. Also if length of t is less than length of s there is no way s can be subsequence of t.

```     private boolean isSubsequenceUtilDP(String s, String t){

boolean [][] dp = new boolean[t.length()+1][s.length()+1];

for(int i=0; i<=t.length(); i++){
dp[i][0] = true;
}
for(int j=1;j<=s.length(); j++){
dp[0][j] = false;
}

for(int i=1; i<=t.length(); i++){
for(int j=1; j<=s.length(); j++){
if(i < j) dp[i][j] = false;

else {
dp[i][j] = t.charAt(i-1) == s.charAt(j-1) ?
dp[i-1][j-1]
: dp[i-1][j];
}
}
}

return dp[t.length()][s.length()];
}
```

The time complexity of dynamic programming solution is O(n * m) where n and m are length of string t and s respectively. Also, there is additional space complexity of O(n * m).

We can reduce this complexity by using stack data structure as the relative position of characters in source and target string should remain same and matched characters can be deleted.

Using Stack

1. Push the characters of source string in reverse order onto the stack.
2. Iterate through the characters of the target string, and check if the character matches with the top element of the stack. If it matches, pop the element from the stack.
3. Obtain the end result – If size of stack is zero, then it returns true, else false.
```public boolean isSubsequence(String s, String t) {
if(s.length()==0 && t.length() > 0)
return true;

if(s.length() > t.length())
return false;

Stack<Character> stack=new Stack<>();
for(int i=s.length()-1;i >=0;i--)
stack.push(s.charAt(i));

for(int i=0; i < t.length();i++){
if(!stack.isEmpty() && t.charAt(i)==stack.peek())
stack.pop();
}
return stack.isEmpty();
}
```

Time Complexity of the stack based solution is O(n + m) and the space Complexity isO(m), where n and m are length of string t and s respectively

The space complexity can be further reduced to O(1) by using two pointers approach.

Two Pointers

Take two pointers i which is used to traverse string t and j, which is used to traverse strings. Increment j whenever there is a match and compare the value of j with the length of source string at the end.

```public boolean isSubsequence(String s, String t)
{
if(s.length() > t.length())
return false;
int i = 0, j = 0;
while(i < t.length() && j < s.length()){
if(t.charAt(i) == s.charAt(j))
j++;
i++;
}
if(j == s.length())
return true;
return false;
}
```

The time Complexity is O(n + m) and the space Complexity is O(1)

Please write to us if something is missing or wrong, we will be happy to fix it.

## Longest Mountain in Array

The mountain at index i in array arris defined such that

`arr[i-N]..arr[i-1]< arr[i] > arr[i+1] arr[i+N] `

where i cannot be 0 and arr.length-1 which means that the index(i) cannot be at the extreme ends in the array (start and end of an array). Given an array A of integers, return the length of the longest mountain.  Return 0 if there is no mountain. Minimum length of a mountain subarray should 3.

Example 1:

```Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.```

## Thought process

Question is to find the mountain which has longest length which means the length of the increasing array ending at arr[i] + the length of the decreasing array starting at arr[i] should be longest among all the mountains in an array, then we can return that length as longest mountain length.

Also if there is a flattening curve as in case of [2,3,3] there is no peak, the flat curve will not be a part of a mountain. The answer for [2,3,3] is 0. Here are couple of inputs and expected answers. This is a good clarifying question in an interview.

Idea is that for each index `i`, we will keep a track of how many numbers are there towards the left of the indexiare in increasing order and how many numbers on the right side of the index i, which are in decreasing order. If the length of the mountain with index `i` has its peak is longer than earlier seen mountains, we update the longest length.

It is important to note that both side subarray should be monotonically increasing and decreasing. As soon as we hit a flat curve (consecutive duplicates numbers), the duplicate elements can not part of the mountain array .

Also note that we jump the left to the next number to the mountain array, because no index in this mountain array will make a bigger mountain than the current one. See why?

### show me the solution

``` public int longestMountain(int[] arr) {

if(arr==null || arr.length<3) return 0;

int left=1;
int len=arr.length-1;
int ans=0;

while(left<=len){

int upHill=0;
int downHill=0;

// if there are duplicates on the left ,
//they wont be the part of the mountain
while(left<=len && arr[left]==arr[left-1]) left++;

while(left<=len && arr[left]>arr[left-1]) {
upHill++;
left++;
}

while(left<=len && arr[left]<arr[left-1]) {
downHill++;
left++;
}

// if the sequence is 2, 3, 3, 5 , then the
// downHill will not be greter than 0 at left = 2
if(upHill>0 && downHill>0) {
ans=Math.max(ans,upHill+downHill+1);
}

}
return ans;
}
```

The time complexity of the implementation is O(n)

.