# 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**

1 | Input: s = "ababa" |

### 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).

### Code

1 | // time:O(n) space:O(n) |

## [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

**from highest to lowest. For simplicity**

*id*`veganFriendlyi`

and `veganFriendly`

take value *1*when it is

*true*, and

*0*when it is

*false*.

**Example**

1 | Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 1, maxPrice = 50, maxDistance = 10 |

### Solution

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

### Code

1 | public class Restaurant implements Comparable<Restaurant>{ |

## [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

**is equal to the sum of the edges’ weights along that path.**

*j***Example**

1 | Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4 |

### 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

1 | public int findTheCity2(int n, int[][] edges, int distanceThreshold) { |

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