# Solution of Weekly Contest 173

## [Easy] [Fail] 1332. Remove Palindromic Subsequences

Given a string `s` consisting only of letters `'a'` and `'b'`. In a single step you can remove one palindromic subsequence from `s`.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string, if it is generated by deleting some characters of a given string without changing its order.

A string is called palindrome if is one that reads the same backward as well as forward.

Example

### Solution

Be careful the meaning of subsequence, which means we don’t need to move string continuously. And, the stirng only contains `a` and `b`, the maximum remove would be two (one for `a` subsequence, one for `b` subsequence).

## [Medium] [pass]1333. Filter Restaurants by Vegan-Friendly, Price and Distance

Given the array `restaurants` where `restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]`. You have to filter the restaurants using three filters.

The `veganFriendly` filter will be either true (meaning you should only include restaurants with `veganFriendlyi` set to true) or false (meaning you can include any restaurant). In addition, you have the filters `maxPrice` and `maxDistance` which are the maximum value for price and distance of restaurants you should consider respectively.

Return the array of restaurant IDs after filtering, ordered by rating from highest to lowest. For restaurants with the same rating, order them by id from highest to lowest. For simplicity `veganFriendlyi` and `veganFriendly` take value 1 when it is true, and 0 when it is false.

Example

### Solution

Customized sorting question. We just need to know what they are saying and solve it.

## [Medium] [TLE] 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

There are `n` cities numbered from `0` to `n-1`. Given the array `edges` where `edges[i] = [fromi, toi, weighti]` represents a bidirectional and weighted edge between cities `fromi` and `toi`, and given the integer `distanceThreshold`.

Return the city with the smallest number of cities that are reachable through some path and whose distance is at most `distanceThreshold`, If there are multiple such cities, return the city with the greatest number.

Notice that the distance of a path connecting cities i and j is equal to the sum of the edges’ weights along that path.

Example

### Solution

During the contest, I spent a lot of time to solve this problem and then failed. After seeing post in the disscussion and found out that I shouldn’t use DFS because they can have shorest path, which contains more neighbors, so I just pass 40 / 52 test cases. For the shorest path problem, we can use Dijkstra and Floyd Warshall algorithms.

### Code

Rank: 2296 / 6103. Solved 1/4 in 1h 30min.