Loading Similar Posts

Entering edit mode

**Overview**

- Given a string of lowercase English letters, return the index of the first occurrence of a unique character in the string using 1-based indexing.
- if the string does not contain any unique character return -1.

**Solution**

- Keep the frequency of each character in a frequency array.
- Now iterate from the start of the string, for each character check its frequency using the frequency array.
- If the frequency of a character is greater than 1, then move on to the next character in the string.
- Else if the frequency of a character is equal to 1, print the answer as the current index( using 1 -based indexing).
- If there is no character with frequency as 1 , the print the answer as -1

Entering edit mode

**Question 2**

`Overview`

- There are n requests given by their request times. There are 3 rules for taking a request to process
- Number of requests processed in any given second is at max
`3.`

- Number of requests processed in any 10-second period is at max
`20.`

- Number of requests processed in any 60-second period is at max
`60.`

- Number of requests processed in any given second is at max
- if any processing request violates any of the rules the request is dropped
- We need to find the number of requests dropped.
- This is an
**implementation Problem**

`Approach`

- Sort the requests times(it not sorted )
- Have 3 to
**two pointer**- Can keep a common right pointer, as it denotes the current index.
- let the time request at the current index
`right`

be`x`

`left_1`

pointer is for rule 1(1 sec).- Denotes the index where a request of time
`x`

started. - if
`(right - left_1) >=3`

drop request at`right`

- Denotes the index where a request of time
`left_2`

pointer is for rule 2(10 sec).- Denotes the leftmost index whose request time is greater than
`x-10`

- if
`(right - left_2) >=20`

drop request at`right`

- Denotes the leftmost index whose request time is greater than
`left_3`

pointer is for rule 2(60 sec).- Denotes the leftmost index whose request time is greater than
`x-60`

- if
`(right - left_3) >=60`

drop request at`right`

-Have a count of non-dropped requests

- Denotes the leftmost index whose request time is greater than

- Return
`arr.size()-count of non dropped requests`

`Complexity:`

- If initially given array is sorted, then
`O(N)`

- Else
`O(NLOGN)`

`Pseudocode:`

```
int solve(vector<int> arr){
sort(arr.begin(),arr.end());
int ans = 0,current_time=0;
int sec_i = 0,sec_10_i = 0,min_i = 0,index = 0;
while(index<arr.size()-1){
index++;
// for 1 sec
if(arr[sec_i] == arr[index] && index-sec_i >=3) continue;
else sec_i = index;
// for 10 sec
while(arr[sec_10_i] <= arr[index] - 10) sec_10_i++;
if(index-sec_10_i >= 20) continue;
// for 1 min
while(arr[min_i] <= arr[index] - 60) min_i++;
if(index-min_i >= 60) continue;
ans++;
}
return arr.size()-ans;
}
```

Loading Similar Posts