| 0821 |[Shortest Distance to a Character](src/main/kotlin/g0801_0900/s0821_shortest_distance_to_a_character/Solution.kt)| Easy | Array, String, Two_Pointers | 168 | 88.00

| 0820 |[Short Encoding of Words](src/main/kotlin/g0801_0900/s0820_short_encoding_of_words/Solution.kt)| Medium | Array, String, Hash_Table, Trie | 231 | 100.00

| 0819 |[Most Common Word](src/main/kotlin/g0801_0900/s0819_most_common_word/Solution.kt)| Easy | String, Hash_Table, Counting | 211 | 83.33

| 0818 |[Race Car](src/main/kotlin/g0801_0900/s0818_race_car/Solution.kt)| Hard | Dynamic_Programming | 123 | 100.00

package g0801_0900.s0818_race_car

import java.util.LinkedList

import java.util.Queue

class Solution {

fun racecar(target: Int): Int {

val queue: Queue<IntArray> = LinkedList()

queue.add(intArrayOf(0, 1, 0))

while (!queue.isEmpty()) {

val arr = queue.poll()

if (arr[0] == target) {

return arr[2]

}

queue.add(intArrayOf(arr[0] + arr[1], 2 * arr[1], 1 + arr[2]))

if (arr[0] + arr[1] > target && arr[1] > 0) {

queue.add(intArrayOf(arr[0], -1, 1 + arr[2]))

}

if (arr[0] + arr[1] < target && arr[1] < 0) {

queue.add(intArrayOf(arr[0], 1, 1 + arr[2]))

}

}

return -1

}

}

818\. Race Car

Hard

Your car starts at position `0` and speed `+1` on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions `'A'` (accelerate) and `'R'` (reverse):

* When you get an instruction `'A'`, your car does the following:

* `position += speed`

* `speed *= 2`

* When you get an instruction `'R'`, your car does the following:

* If your speed is positive then `speed = -1`

* otherwise `speed = 1`Your position stays the same.

For example, after commands `"AAR"`, your car goes to positions `0 --> 1 --> 3 --> 3`, and your speed goes to `1 --> 2 --> 4 --> -1`.

Given a target position `target`, return _the length of the shortest sequence of instructions to get there_.

**Example 1:**

**Input:** target = 3

**Output:** 2

**Explanation:**

The shortest instruction sequence is "AA".

Your position goes from 0 --> 1 --> 3.

**Example 2:**

**Input:** target = 6

**Output:** 5

**Explanation:**

The shortest instruction sequence is "AAARA".

Your position goes from 0 --> 1 --> 3 --> 7 --> 7 --> 6.

**Constraints:**

* <code>1 <= target <= 10⁴</code>

package g0801_0900.s0819_most_common_word

import java.util.Locale

@Suppress("NAME_SHADOWING")

class Solution {

fun mostCommonWord(paragraph: String, banned: Array<String>): String {

var paragraph = paragraph

paragraph = paragraph.replace("\\p{Punct}".toRegex(), " ").lowercase(Locale.getDefault())

val a = paragraph.split(" ".toRegex()).dropLastWhile { it.isEmpty() }.toTypedArray()

for (i in banned.indices) {

banned[i] = banned[i].lowercase(Locale.getDefault())

}

val map: MutableMap<String, Int> = HashMap()

for (s in a) {

val x = map.getOrDefault(s, 0)

map[s] = x + 1

}

for (s in banned) {

map.remove(s)

map.remove("")

}

return map.maxBy { it.value }.key

}

}

819\. Most Common Word

Easy

Given a string `paragraph` and a string array of the banned words `banned`, return _the most frequent word that is not banned_. It is **guaranteed** there is **at least one word** that is not banned, and that the answer is **unique**.

The words in `paragraph` are **case-insensitive** and the answer should be returned in **lowercase**.

**Example 1:**

**Input:** paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]

**Output:** "ball"

**Explanation:** "hit" occurs 3 times, but it is a banned word. "ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. Note that words in the paragraph are not case sensitive, that punctuation is ignored (even if adjacent to words, such as "ball,"), and that "hit" isn't the answer even though it occurs more because it is banned.

**Example 2:**

**Input:** paragraph = "a.", banned = []

**Output:** "a"

**Constraints:**

* `1 <= paragraph.length <= 1000`

* paragraph consists of English letters, space `' '`, or one of the symbols: `"!?',;."`.

* `0 <= banned.length <= 100`

* `1 <= banned[i].length <= 10`

* `banned[i]` consists of only lowercase English letters.

package g0801_0900.s0820_short_encoding_of_words

class Solution {

private class Node {

var nodes = arrayOfNulls<Node>(26)

}

private fun insert(node: Node, word: String): Boolean {

var current: Node? = node

val n = word.length

var flag = false

for (i in n - 1 downTo 0) {

if (current!!.nodes[word[i].code - 'a'.code] == null) {

current.nodes[word[i].code - 'a'.code] = Node()

flag = true

}

current = current.nodes[word[i].code - 'a'.code]

}

return flag

}

fun minimumLengthEncoding(words: Array<String>): Int {

var out = 0

words.sortWith { a: String, b: String -> b.length - a.length }

val node = Node()

for (word in words) {

if (insert(node, word)) {

out += word.length + 1

}

}

return out

}

}

820\. Short Encoding of Words

Medium

A **valid encoding** of an array of `words` is any reference string `s` and array of indices `indices` such that:

* `words.length == indices.length`

* The reference string `s` ends with the `'#'` character.

* For each index `indices[i]`, the **substring** of `s` starting from `indices[i]` and up to (but not including) the next `'#'` character is equal to `words[i]`.

Given an array of `words`, return _the **length of the shortest reference string**_ `s` _possible of any **valid encoding** of_ `words`_._

**Example 1:**

**Input:** words = ["time", "me", "bell"]

**Output:** 10

**Explanation:** A valid encoding would be s = `"time#bell#" and indices = [0, 2, 5`].

words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"

words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"

words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

**Example 2:**

**Input:** words = ["t"]

**Output:** 2

**Explanation:** A valid encoding would be s = "t#" and indices = [0].

**Constraints:**

* `1 <= words.length <= 2000`

* `1 <= words[i].length <= 7`

* `words[i]` consists of only lowercase letters.

package g0801_0900.s0821_shortest_distance_to_a_character

class Solution {

fun shortestToChar(s: String, c: Char): IntArray {

val result = IntArray(s.length)

result.fill(Int.MAX_VALUE)

for (i in s.indices) {

if (s[i] == c) {

result[i] = 0

}

}

for (i in s.indices) {

if (result[i] != 0) {

var j = i - 1

while (j >= 0 && result[j] != 0) {

j--

}

if (j >= 0) {

result[i] = i - j

}

j = i + 1

while (j < s.length && result[j] != 0) {

j++

}

if (j < s.length) {

result[i] = result[i].coerceAtMost(j - i)

}

}

}

return result

}

}

821\. Shortest Distance to a Character

Easy

Given a string `s` and a character `c` that occurs in `s`, return _an array of integers_ `answer` _where_ `answer.length == s.length` _and_ `answer[i]` _is the **distance** from index_ `i` _to the **closest** occurrence of character_ `c` _in_ `s`.

The **distance** between two indices `i` and `j` is `abs(i - j)`, where `abs` is the absolute value function.

**Example 1:**

**Input:** s = "loveleetcode", c = "e"

**Output:** [3,2,1,0,1,0,0,1,2,2,1,0]

**Explanation:** The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).

The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.

The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.

For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.

The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.

**Example 2:**

**Input:** s = "aaab", c = "b"

**Output:** [3,2,1,0]

**Constraints:**

* <code>1 <= s.length <= 10⁴</code>

* `s[i]` and `c` are lowercase English letters.

* It is guaranteed that `c` occurs at least once in `s`.

package g0801_0900.s0818_race_car

import org.hamcrest.CoreMatchers.equalTo

import org.hamcrest.MatcherAssert.assertThat

import org.junit.jupiter.api.Test

internal class SolutionTest {

@Test

fun raceCar() {

assertThat(Solution().racecar(3), equalTo(2))

}

@Test

fun raceCar2() {

assertThat(Solution().racecar(6), equalTo(5))

}

}

package g0801_0900.s0819_most_common_word

import org.hamcrest.CoreMatchers.equalTo

import org.hamcrest.MatcherAssert.assertThat

import org.junit.jupiter.api.Test

internal class SolutionTest {

@Test

fun mostCommonWord() {

assertThat(

Solution()

.mostCommonWord(

"Bob hit a ball, the hit BALL flew far after it was hit.", arrayOf("hit")

),

equalTo("ball")

)

}

@Test

fun mostCommonWord2() {

assertThat(Solution().mostCommonWord("a.", arrayOf()), equalTo("a"))

}

}

package g0801_0900.s0820_short_encoding_of_words

import org.hamcrest.CoreMatchers.equalTo

import org.hamcrest.MatcherAssert.assertThat

import org.junit.jupiter.api.Test

internal class SolutionTest {

@Test

fun minimumLengthEncoding() {

assertThat(

Solution().minimumLengthEncoding(arrayOf("time", "me", "bell")),

equalTo(10)

)

}

@Test

fun minimumLengthEncoding2() {

assertThat(Solution().minimumLengthEncoding(arrayOf("t")), equalTo(2))

}

}

package g0801_0900.s0821_shortest_distance_to_a_character

import org.hamcrest.CoreMatchers.equalTo

import org.hamcrest.MatcherAssert.assertThat

import org.junit.jupiter.api.Test

internal class SolutionTest {

@Test

fun shortestToChar() {

assertThat(

Solution().shortestToChar("loveleetcode", 'e'),

equalTo(intArrayOf(3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0))

)

}

@Test

fun shortestToChar2() {

assertThat(Solution().shortestToChar("aaab", 'b'), equalTo(intArrayOf(3, 2, 1, 0)))

}

}