> For the complete documentation index, see [llms.txt](https://lintcode-solutions.gitbook.io/project/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lintcode-solutions.gitbook.io/project/oj-review/aug-7-2018.md).

# Aug 7, 2018

## String

### `String.substring()`

The **java string substring()** method returns *a part of the string*.

We pass `begin index` and `end index` number position in the java substring method where **start index is inclusive and end index is exclusive**. In other words, start index starts from 0 whereas end index starts from 1.

You can get substring from the given string object by one of the two methods:

1. **`public String substring(int startIndex)`:** This method returns **new String object** containing the substring of the given string from specified **startIndex (inclusive)**.
2. **`public String substring(int startIndex, int endIndex)`:** This method returns **new String object** containing the **substring of the given string from specified startIndex to endIndex**.

In case of string:

* **startIndex:** inclusive
* **endIndex:** exclusive

**Example**:

```java
public class TestSubstring{  
    public static void main(String args[]){  
        String s="SachinTendulkar";  
        System.out.println(s.substring(6));      //Tendulkar  
        System.out.println(s.substring(0,6));    //Sachin  
    }  
}  
```

**Output**:

```
Tendulkar
Sachin
```

### `String` vs `StringBuilder` vs `StringBuffer`

Consider below code with three concatenation functions with three different types of parameters, String, StringBuffer and StringBuilder.

```java
// Java program to demonstrate difference between String,
// StringBuilder and StringBuffer
class Geeksforgeeks
{
    // Concatenates to String
    public static void concat1(String s1)
    {
        s1 = s1 + "forgeeks";
    }
 
    // Concatenates to StringBuilder
    public static void concat2(StringBuilder s2)
    {
        s2.append("forgeeks");
    }
 
    // Concatenates to StringBuffer
    public static void concat3(StringBuffer s3)
    {
        s3.append("forgeeks");
    }
 
    public static void main(String[] args)
    {
        String s1 = "Geeks";
        concat1(s1);  // s1 is not changed
        System.out.println("String: " + s1);
 
        StringBuilder s2 = new StringBuilder("Geeks");
        concat2(s2);  // s2 is changed
        System.out.println("StringBuilder: " + s2);
 
        StringBuffer s3 = new StringBuffer("Geeks");
        concat3(s3);  // s3 is changed
        System.out.println("StringBuffer: " + s3);
    }
}
```

**Output**:

```
String: Geeks
StringBuilder: Geeksforgeeks
StringBuffer: Geeksforgeeks
```

**Explanation:**

1. **Concat1** : In this method, we pass a string "Geeks" and perform "`s1 = s1 + "forgeeks"`". The string passed from `main()` is not changed, this is due to the fact that String is **immutable**. Altering the value of string creates another object and s1 in `concat1()` stores reference of new string. References s1 in `main()` and `concat1()` refer to different strings.
2. **Concat2** : In this method, we pass a string "Geeks" and perform "`s2.append("forgeeks")`" which changes the actual value of the string (in main) to "`Geeksforgeeks`". This is due to the simple fact that **StringBuilder is mutable** and hence changes its value.
3. **Concat3** : StringBuffer is similar to StringBuilder except one difference that **StringBuffer is thread safe**, i.e., **multiple threads can use it without any issue**. The *thread safety brings a penalty of performance*.

**When to use which one :**

* If a string is going to **remain constant** throughout the program, then use String class object because a **String object is immutable**.
* If a **string can change (example: lots of logic and operations in the construction of the string)** and will **only be accessed from a single thread**, using a **StringBuilder** is good enough.
* If a **string can change, and will be accessed from multiple threads**, use a **StringBuffer** because **StringBuffer is synchronous so you have thread-safety**.

## Map 

### **`java.util.HashMap.containsKey()`**

The **`java.util.HashMap.containsKey()`** method is used to **check whether a particular key is being mapped into the HashMap or not**. It takes the key element as a parameter and returns True if that element is mapped in the map.

**Syntax:**

```java
Hash_Map.containsKey(key_element)
```

**Parameters:** The method takes just one parameter *key\_element* that refers to the key whose mapping is supposed to be checked inside a map.

**Return Value:** The method returns boolean true if the presence of the key is detected else false .

Below programs are used to illustrate the working of `java.util.HashMap.containsKey()` Method:

**Program 1:** Mapping **`String Values`** to **`Integer Keys`**.

```java
// Java code to illustrate the containsKey() method
import java.util.*;
 
public class Hash_Map_Demo {
    public static void main(String[] args)
    {
 
        // Creating an empty HashMap
        HashMap<Integer, String> hash_map = new HashMap<Integer, String>();
 
        // Mapping string values to int keys
        hash_map.put(10, "Geeks");
        hash_map.put(15, "4");
        hash_map.put(20, "Geeks");
        hash_map.put(25, "Welcomes");
        hash_map.put(30, "You");
 
        // Displaying the HashMap
        System.out.println("Initial Mappings are: " + hash_map);
 
        // Checking for the key_element '20'
        System.out.println("Is the key '20' present? " + 
        hash_map.containsKey(20));
 
        // Checking for the key_element '5'
        System.out.println("Is the key '5' present? " + 
        hash_map.containsKey(5));
    }
}
```

**Output:**

```
Initial Mappings are: {20=Geeks, 25=Welcomes, 10=Geeks, 30=You, 15=4}
Is the key '20' present? true
Is the key '5' present? false
```

**Program 2:** Mapping **`Integer Values`** to **`String Keys`**.

```java
// Java code to illustrate the containsKey() method
import java.util.*;
 
public class Hash_Map_Demo {
    public static void main(String[] args)
    {
 
        // Creating an empty HashMap
        HashMap<String, Integer> hash_map = new HashMap<String, Integer>();
 
        // Mapping int values to string keys
        hash_map.put("Geeks", 10);
        hash_map.put("4", 15);
        hash_map.put("Geeks", 20);
        hash_map.put("Welcomes", 25);
        hash_map.put("You", 30);
 
        // Displaying the HashMap
        System.out.println("Initial Mappings are: " + hash_map);
 
        // Checking for the key_element 'Welcomes'
        System.out.println("Is the key 'Welcomes' present? " + 
        hash_map.containsKey("Welcomes"));
 
        // Checking for the key_element 'World'
        System.out.println("Is the key 'World' present? " + 
        hash_map.containsKey("World"));
    }
}
```

**Output**:

```
Initial Mappings are: {4=15, Geeks=20, You=30, Welcomes=25}
Is the key 'Welcomes' present? true
Is the key 'World' present? false
```

### `HashMap` vs. `TreeMap` vs. `HashTable` vs. `LinkedHashMap` &#x20;

#### **Map Overview**

There are 4 commonly used  implementations of Map in Java SE - **`HashMap`**, **`TreeMap`**, **`Hashtable`** and **`LinkedHashMap`**. If we use one sentence to describe each implementation, it would be the following:  &#x20;

* **`HashMap`** is **implemented as a hash table**, and **there is no ordering on keys or values**.&#x20;
* **`TreeMap`** is **implemented based on red-black tree structure**, and **it is ordered by the key**.&#x20;
* **`LinkedHashMap`** **preserves the insertion order**.
* &#x20;**`Hashtable`** is **synchronized**, in contrast to HashMap.&#x20;

This gives us the reason that **`HashMap` should be used if it is thread-safe, since `Hashtable` has overhead for synchronization**.&#x20;

#### `TreeMap`

A `TreeMap` is **sorted by keys**. Let's first take a look at the following example to understand the "sorted by keys" idea.

```java
class Dog {
    String color;
    Dog(String c) {
        color = c;
    }
    public boolean equals(Object o) {
        return ((Dog) o).color == this.color;
    }
    public int hashCode() {
        return color.length();
    }
    public String toString(){
        return color + " dog";
    }
}
public class TestTreeMap {
    public static void main(String[] args) {
        Dog d1 = new Dog("red");
        Dog d2 = new Dog("black");
        Dog d3 = new Dog("white");
        Dog d4 = new Dog("white");
        TreeMap treeMap = new TreeMap();
        treeMap.put(d1, 10);
        treeMap.put(d2, 15);
        treeMap.put(d3, 5);
        treeMap.put(d4, 20);
        for (Entry entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + " - " + entry.getValue());
        }
    }
}
```

**Output**:

```java
Exception in thread “main” java.lang.ClassCastException: collection.Dog cannot be cast to java.lang.Comparable
at java.util.TreeMap.put(Unknown Source)
at collection.TestHashMap.main(TestHashMap.java:35)
```

Since `TreeMaps` are sorted by keys, the object for key has to be able to compare with each other, that's why it has to implement **`Comparable`** interface. For example,  you use String as key, because String implements Comparable interface.  Let's change the Dog, and make it comparable. &#x20;

```java
class Dog implements Comparable{
    String color;
    int size;
    Dog(String c, int s) {
        color = c;
        size = s;
    }

    public String toString(){
        return color + " dog";
    }

    @Override
    public int compareTo(Dog o) {
        return  o.size - this.size;
    }
}

public class TestTreeMap {
    public static void main(String[] args) {
        Dog d1 = new Dog("red", 30);
        Dog d2 = new Dog("black", 20);
        Dog d3 = new Dog("white", 10);
        Dog d4 = new Dog("white", 10);
        TreeMap treeMap = new TreeMap();
        treeMap.put(d1, 10);
        treeMap.put(d2, 15);
        treeMap.put(d3, 5);
        treeMap.put(d4, 20);
        for (Entry entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + " - " + entry.getValue());
        }
    }
}
```

**Output**:

```java
red dog – 10
black dog – 15
white dog – 20
```

It is sorted by key, i.e., **dog size** in this case.  If "`Dog d4 = new Dog("white", 10);`" is replaced with "`Dog d4 = new Dog("white", 40);`", the output would be:&#x20;

```java
white dog – 20
red dog – 10
black dog – 15
white dog – 5
```

The reason is that `TreeMap` now uses **`compareTo()`** method to compare keys. Different sizes make different dogs!

#### `HashMap`

If key of the `HashMap` is `self-defined objects`, then `equals()` and `hashCode()` contract need to be followed.&#x20;

```java
class Dog {
    String color;
    Dog(String c) {
      color = c;
    }
    public String toString(){
      return color + " dog";
    }
}
public class TestHashMap {
    public static void main(String[] args) {
        HashMap hashMap = new HashMap();
        Dog d1 = new Dog("red");
        Dog d2 = new Dog("black");
        Dog d3 = new Dog("white");
        Dog d4 = new Dog("white");
        hashMap.put(d1, 10);
        hashMap.put(d2, 15);
        hashMap.put(d3, 5);
        hashMap.put(d4, 20);
        //print size
        System.out.println(hashMap.size());
        //loop HashMap
        for (Entry entry : hashMap.entrySet()) {
            System.out.println(entry.getKey().toString() + " - " + entry.getValue());
        }
    }
}
```

**Output**:

```java
white dog – 5
black dog – 15
red dog – 10
white dog – 20
```

Note here, we add "**white dogs**" twice by mistake, but the `HashMap` takes it. This does not make sense, because now we are confused how many white dogs are really there.  The Dog class should be defined as follows:

```java
class Dog {
    String color;
    Dog(String c) {
        color = c;
    }

    public boolean equals(Object o) {
        return ((Dog) o).color == this.color;
    }
    public int hashCode() {
        return color.length();
    }
    public String toString(){
        return color + " dog";
    }
}
```

Now the output is:

```java
red dog – 10
white dog – 20
black dog – 15
```

The reason is that HashMap doesn't allow two identical elements. By default, the `hashCode()` and `equals()` methods implemented in Object class are used. The default `hashCode()` method gives distinct integers for distinct objects, and the `equals()` method only returns true when  two references refer to the same object. Check out the **`hashCode() and equals() contract`** if this is not obvious to you.&#x20;

#### `LinkedHashMap`

`LinkedHashMap` is a **subclass** of `HashMap`. That means **it inherits the features of HashMap**. In addition, the **linked list preserves the insertion-order**.  Let's replace the HashMap with LinkedHashMap using the same code used for HashMap.&#x20;

```java
class Dog {
    String color;
    Dog(String c) {
        color = c;
    }

    public boolean equals(Object o) {
        return ((Dog) o).color == this.color;
    }
    public int hashCode() {
        return color.length();
    }
    public String toString(){
        return color + " dog";
    }
}

public class TestHashMap {
    public static void main(String[] args) {
        Dog d1 = new Dog("red");
        Dog d2 = new Dog("black");
        Dog d3 = new Dog("white");
        Dog d4 = new Dog("white");
        LinkedHashMap linkedHashMap = new LinkedHashMap();
        linkedHashMap.put(d1, 10);
        linkedHashMap.put(d2, 15);
        linkedHashMap.put(d3, 5);
        linkedHashMap.put(d4, 20);
        for (Entry entry : linkedHashMap.entrySet()) {
            System.out.println(entry.getKey() + " - " + entry.getValue());
        }
    }
}
```

Output is:

```
red dog – 10
black dog – 15
white dog – 20
```

The difference is that if we use `HashMap` the output could be the following - the **insertion order is not preserved**.

```
red dog – 10
white dog – 20
black dog – 15
```

#### `Hashtable`

From Java Doc:  The HashMap class is roughly equivalent to `Hashtable`, **except that it is unsynchronized and permits `nulls`**.

### KMP