Entering edit mode

**Job Roles:** Backend Developer, Frontend Developer

**Avg CTC:** 22.4LPA

**Apply here:** Current Job Openings

Click here to Practice

Submit Problem to OJ

Given a string s, find the length of the longest substring without repeating characters.

**Constraints:**

- 0 <= s.length <= 5 * 10^4
- s consists of English letters, digits, symbols and spaces.

**Examples:**

**Input 1:** s = "abcabcbb"

**Output 1:** 3

**Explanation:** The answer is "abc", with the length of 3.

**Input 2:** s = "bbbbb"

**Output 2:** 1

**Explanation:** The answer is "b", with the length of 1.

**Input 3:** s = "pwwkew"

**Output 3:** 3

**Explanation:** The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Click here to Practice

Submit Problem to OJ

Return Probability of Palindromes for 'n' dice throws where each throw can give result 1 to 6.

**For Ex.** if n=3 then (111),(121),(131),(141),(151),(161),(212),...(666) = 36; total permutations is 216 hence probability is 36/216

Click here to Practice

Submit Problem to OJ

Find number of sub array combinations A[i],A[j] in array A and an int X with the following conditions,

- A[i]=A[j]
- i < j and i != j
i*j is divisible by X

we use 1-index here;

**Example:**

A={2,2,2}, X=2

Combinations if i,j are {1,2},{1,3} and {2,3}

Divisible by X are {1,2} and {2,3}

Hence number of combinations = 2.

Entering edit mode

- Find the probability of palindromes for
`n`

dice throws where each throw can give results 1 to 6.

- The total number of
`n`

digit numbers is`6`

<sup>`n`

</sup>. - A number is a palindrome when the first
`n/2`

digits match with the last`n/2`

digits in reverse order. - For an even number of digits, we can pick the first
`n/2`

digits and then duplicate them to form the rest of`n/2`

digits so we can choose`n/2`

digits. - For an odd number of digits, we can pick first
`(n-1)/2`

digits and then duplicate them to form the rest of`(n-1)/2`

digits so we can choose`(n+1)/2`

digits. - So the probability that an
`n`

digit number is a palindrome is`6`

<sup>ceil(n/2)</sup>`/`

`6`

<sup>n</sup> or 1 /`6`

<sup>floor(n/2)</sup>

Time Complexity: `O(N), N`

is the number of dice throws.

Memory Complexity: `O(1)`

Entering edit mode

**Overview**

- Given a string s consisting of English letters, digits, and symbols, find the length of the longest substring without repeating characters.

**Solution**

- The idea is to scan the string from left to right, and keep track of the maximum length Non-Repeating Character Substring seen so far in res.
- When we traverse the string, to know the length of the current window we need two indexes.
- First is the
**current_index**. The second is the**last_visited_index**which is initialized as 0. - Every time we visit a new character in the string we update
**last_visited_index as max(last_visited_index, last_seen_index[s[cur_char]]).** **last_seen_index**is a map that will be initialized as -1 for all characters in the string and would store the most recent index for each character as we scan along the string.- The answer would
**max(answer, cur_index-last_visited_index+1).**

**Code**

```
ll n;
cin >> n;
string s;
cin >> s;
map<char, ll> mp;
for (ll i = 0; i < n; i++)
{
mp[s[i]] = -1; // initialise with -1
}
ll ans = 0;
ll last_visisted_index = 0;
for (ll i = 0; i < n; i++)
{
last_visisted_index = max(last_visisted_index, mp[s[i]] + 1); // update the last visited vertex
ans = max(ans, i - last_visisted_index + 1); // update the answer
mp[s[i]] = i; // update the most recent index for a charater
}
cout << ans << endl; // print the answer
return;
```

Entering edit mode

- Determine the number of pairs satisfying the given conditions.

Let’s maintain a hashtable,

`count[v][f]`

, which would store the count of how many indexes having a certain value`v`

is divisible by`f`

.Now, let's iterate, and then from each index

`i`

, the other index should be divisible by -`X/gcd(X, i)`

, therefore, we will increment the count by`count[A[i]][X/gcd(X, i)]`

. After counting from each index, we will just update the table and that requires each of us to iterate on all factors of the current index and just increment by`1`

`count[A[i]][factor]`

.Updating requires

`sqrt(n)`

time and the table could be represented by an ordered or unordered map, and the final time complexity should be`O(n*sqrt(n))`

or with an extra log with the ordered map.

```
int ans = 0;
map<int, map<int, int>> count;
for (int i = 0; i < n; i++) {
if (count.find(arr[i]) != count.end()) {
int q = x / __gcd(x, i + 1);
ans += count[arr[i]][q];
}
else {
map<int, int>mm;
count[arr[i]] = mm;
}
addDivisors(i + 1, count[arr[i]]); //sqrt(n) operation
}
cout << ans << endl;
```

Loading Similar Posts