# LeetCode 535: Encode and Decode TinyURL

## Problem Restatement

We need to design a class that can shorten a long URL and later recover the original URL.

The class has two methods:

```python
encode(longUrl)
```

and:

```python
decode(shortUrl)
```

`encode` receives a valid long URL and returns a tiny URL.

`decode` receives a tiny URL generated by the same object and returns the original long URL.

The problem does not restrict the algorithm. It only requires that a URL encoded by the object can be decoded back to the original URL. The statement also guarantees that `decode` is called only with a short URL created by the same object.

## Input and Output

| Method | Input | Output |
|---|---|---|
| `encode` | A long URL string | A short URL string |
| `decode` | A short URL string | The original long URL |

Constraints:

| Item | Constraint |
|---|---|
| URL length | `1 <= url.length <= 10^4` |
| URL validity | The input URL is guaranteed to be valid |

## Examples

Suppose the input URL is:

```python
url = "https://leetcode.com/problems/design-tinyurl"
```

We call:

```python
codec = Codec()
tiny = codec.encode(url)
```

The tiny URL can be any valid string chosen by our implementation, for example:

```python
"https://tinyurl.com/1"
```

Then:

```python
codec.decode(tiny)
```

must return:

```python
"https://leetcode.com/problems/design-tinyurl"
```

The exact short URL does not matter. The round trip matters:

```python
decode(encode(url)) == url
```

## First Thought: Return the Original URL

Since there is no restriction on the algorithm, one trivial idea is:

```python
encode(longUrl) returns longUrl
decode(shortUrl) returns shortUrl
```

This technically preserves the URL, but it defeats the purpose of a URL shortener.

A better solution should return a shorter string and store enough information to recover the original URL.

## Key Insight

A short URL does not need to contain the whole original URL.

It only needs to contain a key.

We can store this mapping:

```python
key -> longUrl
```

Then the short URL is:

```python
base_url + key
```

For example:

```python
"https://tinyurl.com/" + "1"
```

When decoding, we extract the key from the short URL and look up the original URL in the hash map.

A simple counter gives us unique keys:

```python
1, 2, 3, 4, ...
```

This avoids collision handling and keeps the implementation small.

## Algorithm

Maintain:

```python
self.code_to_url
self.next_id
self.base
```

`self.code_to_url` maps generated codes to original URLs.

`self.next_id` gives each new URL a unique code.

`self.base` is the prefix used for short URLs.

For `encode(longUrl)`:

1. Convert `self.next_id` to a string code.
2. Store `code -> longUrl`.
3. Increment `self.next_id`.
4. Return `self.base + code`.

For `decode(shortUrl)`:

1. Remove the base prefix from `shortUrl`.
2. Use the remaining code to look up the long URL.
3. Return the stored URL.

## Correctness

Every call to `encode` assigns the current counter value as the code. The counter increases after each assignment, so no two encoded URLs receive the same code.

The algorithm stores the exact original URL under that code in `code_to_url`.

The short URL returned by `encode` is the base prefix followed by the code. When `decode` receives this short URL, it removes the same base prefix and recovers the same code.

Since `code_to_url[code]` stores the original `longUrl`, `decode` returns exactly the URL that was passed to `encode`.

Therefore, for every encoded URL:

```python
decode(encode(longUrl)) == longUrl
```

## Complexity

Let `L` be the length of the URL.

| Operation | Time | Space |
|---|---:|---:|
| `encode` | `O(L)` | `O(L)` |
| `decode` | `O(1)` average lookup, plus string slicing | `O(1)` extra |

The stored map uses total space proportional to the total length of all encoded long URLs.

## Implementation

```python
class Codec:
    def __init__(self):
        self.base = "http://tinyurl.com/"
        self.next_id = 1
        self.code_to_url = {}

    def encode(self, longUrl: str) -> str:
        code = str(self.next_id)
        self.next_id += 1

        self.code_to_url[code] = longUrl

        return self.base + code

    def decode(self, shortUrl: str) -> str:
        code = shortUrl[len(self.base):]
        return self.code_to_url[code]
```

## Code Explanation

The constructor initializes the service:

```python
self.base = "http://tinyurl.com/"
self.next_id = 1
self.code_to_url = {}
```

The base string is only a prefix. It does not need to be a real working domain for this LeetCode problem.

In `encode`, we generate a code from the counter:

```python
code = str(self.next_id)
self.next_id += 1
```

Then we store the mapping:

```python
self.code_to_url[code] = longUrl
```

Finally, we return the tiny URL:

```python
return self.base + code
```

In `decode`, we recover the code by slicing off the base prefix:

```python
code = shortUrl[len(self.base):]
```

Then we return the original URL:

```python
return self.code_to_url[code]
```

## Optional Improvement: Reuse the Same Short URL

The simple counter solution creates a new short URL each time, even if the same long URL is encoded again.

We can add another map:

```python
longUrl -> code
```

Then repeated calls with the same URL return the same short URL.

```python
class Codec:
    def __init__(self):
        self.base = "http://tinyurl.com/"
        self.next_id = 1
        self.code_to_url = {}
        self.url_to_code = {}

    def encode(self, longUrl: str) -> str:
        if longUrl in self.url_to_code:
            return self.base + self.url_to_code[longUrl]

        code = str(self.next_id)
        self.next_id += 1

        self.url_to_code[longUrl] = code
        self.code_to_url[code] = longUrl

        return self.base + code

    def decode(self, shortUrl: str) -> str:
        code = shortUrl[len(self.base):]
        return self.code_to_url[code]
```

This is not required by the problem, but it is closer to how a real URL shortener would usually behave.

## Testing

```python
def run_tests():
    codec = Codec()

    url1 = "https://leetcode.com/problems/design-tinyurl"
    short1 = codec.encode(url1)
    assert codec.decode(short1) == url1

    url2 = "https://example.com/a/very/long/path?x=1&y=2"
    short2 = codec.encode(url2)
    assert codec.decode(short2) == url2

    assert short1 != short2

    url3 = "https://a.com"
    short3 = codec.encode(url3)
    assert codec.decode(short3) == url3

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard URL | Checks basic round trip |
| URL with path and query | Confirms the whole string is preserved |
| Different URLs | Confirms different generated codes |
| Short valid URL | Checks small input |