LeetCode 1003. Check If Word Is Valid After Substitutions

  Link:- https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/

Summary:

Given a string s, determine if it is valid.

A string s is valid if, starting with an empty string t = "", you can transform t into s after performing the following operation any number of times:

Insert string "abc" into any position in t. More formally, t becomes tleft + "abc" + tright, where t == tleft + tright. Note that tleft and tright may be empty.

Return true if s is a valid string, otherwise, return false. 

For Example:

Input:

s = "aabcbc"

Output:

true

Logic:

This can be solved with the stack. Traverse string and if s[i]!= 'c' then insert into stack.

Else, check if stack element at the top and next to the top is 'b' and 'a' respectively or not.

if no: return false, else remove the top two elements of the stack.

Repeat the above steps.

At last, check if the stack is empty or not.

Time Complexity:

O(n)

To view my solution:

https://github.com/shivam04/codes/blob/master/leetcode/check-if-word-is-valid-after-substitutions.cpp

LeetCode 1530. Number of Good Leaf Nodes Pairs

 Link:- https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/

Summary:

Given a root of the binary tree and an integer distance. Find the number of pairs of leaves such that the shortest path between them is less than or equal to distance.  

For Example:

Input:

root = [1,2,3,null,4], distance = 3

Output:

1

Logic:

Convert the binary tree into a graph using DFS and find all the leaves in that DFS traversal.

Run other DFS from each leaf and check if the shortest distance between current leave and other leaf is less than or equal to distance or not. 

If yes:

ans++

Finally, return ans/2.

Why ans/2?

As we run DFS from each leaf, we end up computing the same pair of leaves twice.

Time Complexity:

O(n^2)

To view my solution:

https://github.com/shivam04/codes/blob/master/leetcode/number-of-good-leaf-nodes-pairs.cpp