Hello all!
I’m trying to solve this problem link
i have this solution
solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin() , x.end()
#define db double
#define pb push_back
const int mod = (int)1e9+7;
#define f first
#define s second
void ok() {
int n,k;
cin >> n ;
vector<int>v(n);
for(int i=0;i<n;i++){
cin >> v[i];
}
unordered_set<int>st;
int i=0,j=0;
int ans = 1;
while(j<n){
if(st.count(v[j])){
ans = max(ans,j-i);
while(v[i]!=v[j]){
st.erase(v[i++]);
}
i++;
}
else{
st.insert(v[j]);
}
j++;
}
ans = max(ans,j-i);
cout<<ans<<"\n";
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
int c = 0;
while (t--) {
ok();
}
return 0;
}
it passes all the test cases except one which gives TLE.
It’s been a days find out the reason for tle.
Any help will be appreciated
Haven’t read your Solution yet.
But, here’s my approach:
Use sliding window, and use hashing for same elements seen after wards:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;cin>>n;
vector<int>arr(n);
for(int i=0;i<n;i++) cin>>arr[i];
map<int,int> m;
int i=1,st=0;
m[arr[0]]=1; //first element is seen here
int f=0;
int res=INT_MIN;
while(i<n)
{
if(m[arr[i]]==0) //check if we encounter already seen element
{m[arr[i]]=1;i++;}
else if(m[arr[i]]==1 && i-st>1)
{
res=max(res,i-st);m[arr[st]]--;st++; //stuff here
f=1;
}
else
{
res=max(res,i-st);
m[arr[st]]=1;
st=i;
i++;
}
}
if(res==INT_MIN || f==0) //if all are unique
res=i-st;
cout<<res<<"\n";
return 0;
}
EDIT: Saw your code, I think if you keep checking the count again and agian, it will give TLE, use map and check if you already seen that element.
1 Like
For this test case :-
6
1 1 3 4 5 6
Output:- 5
your output:- 1
If understood correctly we can rearrange the song sequence if that’s the case then your code is wrong .
If we cannot rearrange the natural order of song sequence then your code is right as it is not clearly mentioned in the given problem.
No you can’t rearrange the sequence read carefully
longest sequence of successive songs where each song is unique
1 Like
aah, good hack. I coded way too quickly. You need to check for adjacent elements to be equal too.
Heres my code :-
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
// import java.util.Scanner;
import java.util.StringTokenizer;
class songSequence{
static class FastReader
{
BufferedReader br;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}
long nextLong()
{
return Long.parseLong(next());
}
double nextDouble()
{
return Double.parseDouble(next());
}
String nextLine()
{
String str = "";
try
{
str = br.readLine();
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}
}
public static void main(String[] args) {
FastReader s =new FastReader();
int size = s.nextInt();
int []arr = new int[size];
for(int i=0;i<size;i++)
arr[i] = s.nextInt();
HashSet <Integer> hs =new HashSet<Integer>();
int maximum = Integer.MIN_VALUE;
int count;
for(int i=0;i<size;i++){
count=0;
for(int j=i;j<size;j++){
if(hs.contains(arr[j]))
j=size;
else
count++;
maximum = Math.max(maximum,count);
hs.add(arr[j]);
}
hs.clear();
}
System.out.println(maximum);
}
}
1 Like