# Encode and Decode TinyURL
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/encode-and-decode-tinyurl)
Canonical: https://scaleengineer.com/dsa/problems/encode-and-decode-tinyurl
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Data structures:** Hash Table, String
**Companies:** [Shopify](https://scaleengineer.com/companies/shopify)
---
## Problem
> Note: This is a companion problem to the [System Design](https://leetcode.com/discuss/interview-question/system-design/) problem: [Design TinyURL](https://leetcode.com/discuss/interview-question/124658/Design-a-URL-Shortener-%28-TinyURL-%29-System/).

TinyURL is a URL shortening service where you enter a URL such as `https://leetcode.com/problems/design-tinyurl` and it returns a short URL such as `http://tinyurl.com/4e9iAk`. Design a class to encode a URL and decode a tiny URL.

There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Implement the `Solution` class:

* `Solution()` Initializes the object of the system.
* `String encode(String longUrl)` Returns a tiny URL for the given `longUrl`.
* `String decode(String shortUrl)` Returns the original long URL for the given `shortUrl`. It is guaranteed that the given `shortUrl` was encoded by the same object.

**Example 1:**

**Input:** url = "https://leetcode.com/problems/design-tinyurl"
**Output:** "https://leetcode.com/problems/design-tinyurl"

**Explanation:**
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.

**Constraints:**

* `1 <= url.length <= 104`
* `url` is guranteed to be a valid URL.

# Approaches
## Random Fixed-Length Code Generation
This approach generates a random alphanumeric string of a fixed length (e.g., 6 characters) to serve as the unique key for each long URL. To handle potential collisions (where a newly generated random code is already in use), it retries the generation process until a unique code is found.
**Time:** `encode`: O(L) on average, where L is the length of the long URL. However, the worst-case time is unbounded due to the random generation loop. `decode`: O(S), where S is the length of the short URL, for string parsing and map lookup. · **Space:** O(N * L), where N is the number of unique URLs encoded and L is the average length of a URL. We need to store two maps.
**Pros:** The generated short URLs are not predictable, which can be a desirable security feature.; The length of the short URL's path is fixed.
**Cons:** The `encode` operation has a non-deterministic time complexity. In the worst-case scenario, where many collisions occur, it could loop for a long time before finding a unique code.; Performance degrades significantly as the number of stored URLs increases, because the probability of collision rises.; It requires two maps to store the bidirectional relationship, increasing space usage compared to counter-based approaches that can derive the code from an ID.
### Explanation
When `encode(longUrl)` is called, we first check if we have already generated a short URL for this `longUrl`. If so, we return the stored short URL.

Otherwise, we enter a loop. In each iteration, we generate a random string of a fixed length using a predefined set of characters (e.g., 'a'-'z', 'A'-'Z', '0'-'9'). We then check if this randomly generated string (the `code`) has already been used as a key in our map. If the `code` is unique, we break the loop and store the mapping from this `code` to the `longUrl`, and also the reverse mapping from `longUrl` to the `code` for future lookups. The final short URL is constructed by appending this unique `code` to a base URL like `http://tinyurl.com/`.

The `decode(shortUrl)` function simply extracts the `code` from the `shortUrl` and looks it up in our map to retrieve the original `longUrl`.

```java
public class Codec {
    Map<String, String> codeToUrl = new HashMap<>();
    Map<String, String> urlToCode = new HashMap<>();
    static final String BASE_HOST = "http://tinyurl.com/";
    static final String CHARS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    static final int CODE_LENGTH = 6;
    Random rand = new Random();

    public String encode(String longUrl) {
        if (urlToCode.containsKey(longUrl)) {
            return BASE_HOST + urlToCode.get(longUrl);
        }
        String code;
        do {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < CODE_LENGTH; i++) {
                sb.append(CHARS.charAt(rand.nextInt(CHARS.length())));
            }
            code = sb.toString();
        } while (codeToUrl.containsKey(code));

        codeToUrl.put(code, longUrl);
        urlToCode.put(longUrl, code);
        return BASE_HOST + code;
    }

    public String decode(String shortUrl) {
        return codeToUrl.get(shortUrl.replace(BASE_HOST, ""));
    }
}
```
### Algorithm
- **Encode(`longUrl`)**:
  1. Check if the `longUrl` has been encoded before by looking it up in a `urlToCode` map. If yes, return the existing short URL.
  2. If not, start a loop:
     a. Generate a random alphanumeric string (`code`) of a fixed length (e.g., 6).
     b. Check if this `code` already exists as a key in a `codeToUrl` map.
     c. If it's unique, exit the loop. Otherwise, repeat.
  3. Store the new mapping in both maps: `codeToUrl.put(code, longUrl)` and `urlToCode.put(longUrl, code)`.
  4. Construct the full short URL by prepending a base host (e.g., `http://tinyurl.com/`) to the `code` and return it.
- **Decode(`shortUrl`)**:
  1. Extract the `code` from the `shortUrl` by removing the base host prefix.
  2. Look up this `code` in the `codeToUrl` map to find the original `longUrl`.
  3. Return the `longUrl`.

## Using an Incrementing Counter
This is a straightforward approach where we use a simple integer counter to generate a unique ID for each new URL. The short URL is created by simply using the string representation of this ID as the path.
**Time:** `encode`: O(L) for map operations, where L is the length of the long URL. `decode`: O(S) for string parsing, where S is the length of the short URL. · **Space:** O(N * L), where N is the number of unique URLs and L is their average length.
**Pros:** Very simple to implement and understand.; Guarantees a unique short URL for every new long URL without any risk of collision during generation.; The `encode` operation is fast and deterministic.
**Cons:** The generated short URLs are sequential and predictable (e.g., `.../1`, `.../2`, `.../3`), which might be undesirable for security or aesthetic reasons.; The length of the short URL's path grows as the counter increases (e.g., from 1 digit to 2, 2 to 3, etc.), which contradicts the 'tiny' aspect over time for a large number of URLs.
### Explanation
We maintain a global counter, initialized to 0. We also use two maps: one to map the counter's ID to the long URL (`idToUrl`) and another to map the long URL back to its ID (`urlToId`) to handle duplicate encoding requests efficiently.

When `encode(longUrl)` is called, we first check the `urlToId` map. If the URL is already present, we retrieve its ID and construct the short URL. If it's a new URL, we increment the counter, store the new `longUrl` with the new counter value in both maps, and then use the counter's value as the short code.

The short URL is formed by `http://tinyurl.com/` followed by the counter's string representation.

`decode(shortUrl)` works by parsing the ID from the end of the `shortUrl`, converting it back to an integer, and looking it up in the `idToUrl` map.

```java
public class Codec {
    private Map<Integer, String> idToUrl = new HashMap<>();
    private Map<String, Integer> urlToId = new HashMap<>();
    private int counter = 0;
    private static final String BASE_HOST = "http://tinyurl.com/";

    public String encode(String longUrl) {
        if (urlToId.containsKey(longUrl)) {
            return BASE_HOST + urlToId.get(longUrl);
        }
        counter++;
        idToUrl.put(counter, longUrl);
        urlToId.put(longUrl, counter);
        return BASE_HOST + counter;
    }

    public String decode(String shortUrl) {
        int id = Integer.parseInt(shortUrl.replace(BASE_HOST, ""));
        return idToUrl.get(id);
    }
}
```
### Algorithm
- **Encode(`longUrl`)**:
  1. Check if the `longUrl` exists in a `urlToId` map. If so, retrieve its ID and return the corresponding short URL.
  2. If it's a new URL, increment a global `counter`.
  3. Store the new mappings: `idToUrl.put(counter, longUrl)` and `urlToId.put(longUrl, counter)`.
  4. Construct the short URL by appending the `counter`'s decimal string representation to the base host (e.g., `http://tinyurl.com/123`).
  5. Return the short URL.
- **Decode(`shortUrl`)**:
  1. Extract the ID string from the `shortUrl`.
  2. Convert the ID string to an integer.
  3. Look up this integer ID in the `idToUrl` map to get the original `longUrl`.
  4. Return the `longUrl`.

## Counter with Base-62 Conversion
This approach enhances the simple counter method by converting the numeric ID into a base-62 string. The base-62 system uses 62 characters (`a-z`, `A-Z`, `0-9`). This results in much shorter, non-sequential-looking URLs while retaining the benefits of a unique, collision-free counter.
**Time:** `encode`: O(L + log_62(N)), where L is the length of the long URL and N is the number of URLs stored. The log term from base conversion is negligible. `decode`: O(S), where S is the length of the short URL's code. · **Space:** O(N * L), where N is the number of unique URLs and L is their average length.
**Pros:** Guarantees unique, collision-free, and deterministic encoding.; Produces very short URLs that are not obviously sequential.; Highly scalable; can support billions of URLs with short codes (e.g., 6 characters can map to over 56 billion URLs).; Both `encode` and `decode` operations are very fast.
**Cons:** The implementation is slightly more complex due to the need for base conversion logic.; While not strictly sequential, the generated codes still follow a predictable pattern if one knows the algorithm.
### Explanation
Similar to the simple counter approach, we use a counter to generate a unique integer ID for each new URL. The key difference is in how we form the short code. Instead of using the decimal representation of the ID, we convert it to a base-62 representation.

The `encode` function gets a unique ID, converts this ID to a base-62 string, and stores the mapping between the ID and the long URL. The `decode` function takes a short URL, extracts the base-62 code, converts it back to the original integer ID, and then retrieves the long URL from the map.

This method is highly efficient and scalable. For example, a 6-character code can represent over 56 billion (62^6) unique URLs, ensuring the 'tiny' aspect is maintained for a very large number of entries.

```java
public class Codec {
    private Map<Integer, String> idToUrl = new HashMap<>();
    private Map<String, Integer> urlToId = new HashMap<>();
    private int counter = 0;
    private static final String BASE_HOST = "http://tinyurl.com/";
    private static final String ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

    public String encode(String longUrl) {
        if (urlToId.containsKey(longUrl)) {
            return BASE_HOST + base62Encode(urlToId.get(longUrl));
        }
        counter++;
        idToUrl.put(counter, longUrl);
        urlToId.put(longUrl, counter);
        return BASE_HOST + base62Encode(counter);
    }

    private String base62Encode(int n) {
        if (n == 0) return String.valueOf(ALPHABET.charAt(0));
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            sb.append(ALPHABET.charAt(n % 62));
            n /= 62;
        }
        return sb.reverse().toString();
    }

    public String decode(String shortUrl) {
        String code = shortUrl.replace(BASE_HOST, "");
        int id = base62Decode(code);
        return idToUrl.get(id);
    }

    private int base62Decode(String code) {
        int id = 0;
        for (int i = 0; i < code.length(); i++) {
            id = id * 62 + ALPHABET.indexOf(code.charAt(i));
        }
        return id;
    }
}
```
### Algorithm
- **Encode(`longUrl`)**:
  1. Check if the `longUrl` exists in a `urlToId` map. If so, retrieve its ID.
  2. If not, increment a global `counter` and store the new mappings: `idToUrl.put(counter, longUrl)` and `urlToId.put(longUrl, counter)`. Use this new `counter` value as the ID.
  3. Convert the integer ID to a base-62 string `code`. This involves repeatedly taking the ID modulo 62 to find the next character and then dividing the ID by 62, until the ID becomes 0.
  4. Return the short URL formed by `BASE_HOST + code`.
- **Decode(`shortUrl`)**:
  1. Extract the base-62 `code` from the `shortUrl`.
  2. Convert the `code` back to its integer ID. This involves iterating through the code's characters and calculating `id = id * 62 + char_value`.
  3. Look up the decoded ID in the `idToUrl` map to retrieve the original `longUrl`.
  4. Return the `longUrl`.

# Solutions
### Java

```java
public class Encode_and_Decode_TinyURL { class Codec { private static final String BASE_HOST = "http://tinyurl.com/" ; private static final String SEED = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" ; // maintain 2 mapping relationships, could be in memory or database or disk file private Map < String , String > keyToUrl = new HashMap <>(); private Map < String , String > urlToKey = new HashMap <>(); // Encodes a URL to a shortened URL. public String encode ( String longUrl ) { if ( urlToKey . containsKey ( longUrl )) { // could also be collision and hash to different tinyUrl return BASE_HOST + urlToKey . get ( longUrl ); } String key = null ; do { StringBuilder sb = new StringBuilder (); for ( int i = 0 ; i < 6 ; i ++) { int r = ( int )( Math . random () * SEED . length ()); sb . append ( SEED . charAt ( r )); } key = sb . toString (); } while ( keyToUrl . containsKey ( key )); keyToUrl . put ( key , longUrl ); urlToKey . put ( longUrl , key ); return BASE_HOST + key ; } // Decodes a shortened URL to its original URL. public String decode ( String shortUrl ) { return keyToUrl . get ( shortUrl . replace ( BASE_HOST , "" )); } } } ############ public class Codec { private Map < String , String > m = new HashMap <>(); private int idx = 0 ; private String domain = "https://tinyurl.com/" ; // Encodes a URL to a shortened URL. public String encode ( String longUrl ) { String v = String . valueOf (++ idx ); m . put ( v , longUrl ); return domain + v ; } // Decodes a shortened URL to its original URL. public String decode ( String shortUrl ) { int i = shortUrl . lastIndexOf ( '/' ) + 1 ; return m . get ( shortUrl . substring ( i )); } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.decode(codec.encode(url));
```

### Python

```python
class Codec : def __init__ ( self ): self . urlMap = {} self . id = 0 def encode ( self , longUrl : str ) -> str : """Encodes a URL to a shortened URL.""" self . id += 1 shortUrlKey = str ( self . id ) self . urlMap [ shortUrlKey ] = longUrl return "http://tinyurl.com/" + shortUrlKey def decode ( self , shortUrl : str ) -> str : """Decodes a shortened URL to its original URL.""" shortUrlKey = shortUrl . split ( '/' )[ - 1 ] return self . urlMap . get ( shortUrlKey , None ) # Your Codec object will be instantiated and called as such: # codec = Codec() # codec.decode(codec.encode(url)) ############ ''' >>> "https://leetcode.ca/2017-05-18-535-Encode-and-Decode-TinyURL".encode() b'https://leetcode.ca/2017-05-18-535-Encode-and-Decode-TinyURL' >>> hashlib.md5("https://leetcode.ca/2017-05-18-535-Encode-and-Decode-TinyURL".encode()) <md5 _hashlib.HASH object @ 0x105cb89b0> >>> hashlib.md5("https://leetcode.ca/2017-05-18-535-Encode-and-Decode-TinyURL".encode()).hexdigest() '4ee0a628f5bb692be5c56af22bc4ec64' ''' import hashlib class Codec : # simple md5 hash def __init__ ( self ): self . urlMap = {} def encode ( self , longUrl : str ) -> str : """Encodes a URL to a shortened URL.""" # Using MD5 hash for simplicity. You can choose other hash functions as well. urlHash = hashlib . md5 ( longUrl . encode ()). hexdigest ()[: 6 ] # Truncate hash for shorter URL if urlHash not in self . urlMap : self . urlMap [ urlHash ] = longUrl return "http://tinyurl.com/" + urlHash def decode ( self , shortUrl : str ) -> str : """Decodes a shortened URL to its original URL.""" urlHash = shortUrl . split ( '/' )[ - 1 ] return self . urlMap . get ( urlHash , None ) ############ class Codec : BASE = 62 UPPERCASE_OFFSET = 55 LOWERCASE_OFFSET = 61 DIGIT_OFFSET = 48 num_sender = 0 url = {} def encode ( self , longUrl ): """Encodes a URL to a shortened URL. :type longUrl: str :rtype: str """ if Codec . num_sender == 0 : Codec . url [ Codec . num_sender ] = longUrl return '0' s_url = '' while Codec . num_sender > 0 : tail = Codec . num_sender % Codec . BASE s_url = self . parse_chr ( tail ) + s_url Codec . num_sender //= Codec . BASE Codec . url [ Codec . num_sender ] = longUrl Codec . num_sender += 1 return s_url def decode ( self , shortUrl ): """Decodes a shortened URL to its original URL. :type shortUrl: str :rtype: str """ num = 0 for i , char in enumerate ( reversed ( shortUrl )): num += self . parse_ord ( char ) * ( Codec . BASE ** i ) return Codec . url [ num ] def parse_ord ( self , char ): if char . isdigit (): return ord ( char ) - Codec . DIGIT_OFFSET elif char . islower (): return ord ( char ) - Codec . LOWERCASE_OFFSET elif char . isupper (): return ord ( char ) - Codec . UPPERCASE_OFFSET else : raise ValueError ( '%s is not a valid character' % char ) def parse_chr ( self , integer ): if integer < 10 : return chr ( integer + DIGIT_OFFSET ) elif 10 <= integer <= 35 : return chr ( integer + UPPERCASE_OFFSET ) elif 36 <= integer < 62 : return chr ( integer + LOWERCASE_OFFSET ) else : raise ValueError ( '%d is not a valid integer in the range of base %d' % ( integer , Codec . BASE )) # Trie class Codec : BASE = 62 num_sender = 0 ALNUM = string . ascii_letters + '0123456789' d_map = { c : i for i , c in enumerate ( ALNUM )} url = {} def encode ( self , longUrl ): pk = Codec . num_sender s_url = '' while pk > 0 : pk , tail = divmod ( pk , Codec . BASE ) s_url = Codec . ALNUM [ tail ] + s_url Codec . url [ pk ] = longUrl Codec . num_sender += 1 if pk == 0 : s_url = Codec . ALNUM [ 0 ] return s_url def decode ( self , shortUrl ): pk = sum ( Codec . d_map [ c ] * Codec . BASE ** i for i , c in enumerate ( reversed ( shortUrl ))) return Codec . url [ pk ]
```

### CPP

```cpp
class Solution { public: // Encodes a URL to a shortened URL. string encode ( string longUrl ) { string v = to_string ( ++ idx ); m [ v ] = longUrl ; return domain + v ; } // Decodes a shortened URL to its original URL. string decode ( string shortUrl ) { int i = shortUrl . rfind ( '/' ) + 1 ; return m [ shortUrl . substr ( i , shortUrl . size () - i )]; } private: unordered_map < string , string > m ; int idx = 0 ; string domain = "https://tinyurl.com/" ; }; // Your Solution object will be instantiated and called as such: // Solution solution; // solution.decode(solution.encode(url));
```