A hiker can go down a valley (D units) take rest and come out or go even deeper for another D units as much as he wants and come up. He can also goes up to a mountain (U units) and keeps climbing another units after a small break and goes down.
We want to know how many times a hiker goes down to a valley after he successfully emerging out of it.
Example:
UUDDUDDU -→ Ans = 1 time
DUDUDUDU-→ Ans = 4 times
UDDDUUUDU-→ Ans = 2 times
Solution:
This is a perfect example for stack data structure
We want to check each action he takes (either U or D) and then we will save it in the stack. But ever time there is item in the stack and it is the opposite of what we get when we iterate from the string, we pop it out other wise we keep stacking it.
We keep the count of how many D we see while the stack is empty.
public int solution(string str) {
char[] A = str.ToCharArray();
int result = 0;
Stack<string> stack = new Stack<string>();
for (int i = 0; i < A.Length; i++) {
if(stack.Count == 0) {
if (A[i].ToString().Equals("D"))
result++;
}
if (A[i].ToString().Equals("D")) {
if (stack.Count != 0) {
if (stack.Peek().Equals("U"))
stack.Pop();
else
stack.Push("D");
}
else
stack.Push("D");
}
//Do the exact opposite for U
else if (A[i].ToString().Equals("U")) {
if (stack.Count != 0 ) {
if(stack.Peek().Equals("D"))
stack.Pop();
else
stack.Push("U");
}
else
stack.Push("U");
}
}
return result;
}
}
}