In this HackerEarth Partial Digit Sequence problem solution You are given an array A of length N. The partial digit subsequence of an array A is a subsequence of integers in which each consecutive integers have at least 1 digit in common. You are required to find the length of the longest partial digit subsequence from the given array.
HackerEarth Partial Digit Sequence problem solution.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;
public class Solution{
public static void main(String[] args) {
new Thread(null, new Runnable() {
public void run() {
new Solution().solve();
}
}, "1", 1 << 26).start();
}
void solve() {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
ScanReader in = new ScanReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
PARTIAL_DIGIT_SEQUENCE solver = new PARTIAL_DIGIT_SEQUENCE();
solver.solve(1, in, out);
out.close();
}
static class PARTIAL_DIGIT_SEQUENCE {
public void solve(int testNumber, ScanReader in, PrintWriter out) {
int n = in.scanInt();
int[] ans = new int[10];
for (int i = 0; i < n; i++) {
long temp = in.scanLong();
boolean[] digits = new boolean[10];
while (temp > 0) {
digits[(int) (temp % 10)] = true;
temp /= 10;
}
int max = 0;
for (int j = 0; j < 10; j++) if (digits[j]) max = Math.max(ans[j], max);
for (int j = 0; j < 10; j++) if (digits[j]) ans[j] = max + 1;
}
int answer = 0;
for (int i = 0; i < 10; i++) answer = Math.max(answer, ans[i]);
out.println(answer);
}
}
static class ScanReader {
private byte[] buf = new byte[4 * 1024];
private int index;
private BufferedInputStream in;
private int total;
public ScanReader(InputStream inputStream) {
in = new BufferedInputStream(inputStream);
}
private int scan() {
if (index >= total) {
index = 0;
try {
total = in.read(buf);
} catch (Exception e) {
e.printStackTrace();
}
if (total <= 0) return -1;
}
return buf[index++];
}
public int scanInt() {
int integer = 0;
int n = scan();
while (isWhiteSpace(n)) n = scan();
int neg = 1;
if (n == '-') {
neg = -1;
n = scan();
}
while (!isWhiteSpace(n)) {
if (n >= '0' && n <= '9') {
integer *= 10;
integer += n - '0';
n = scan();
}
}
return neg * integer;
}
private boolean isWhiteSpace(int n) {
if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
else return false;
}
public long scanLong() {
long integer = 0;
int n = scan();
while (isWhiteSpace(n)) n = scan();
int neg = 1;
if (n == '-') {
neg = -1;
n = scan();
}
while (!isWhiteSpace(n)) {
if (n >= '0' && n <= '9') {
integer *= 10;
integer += n - '0';
n = scan();
}
}
return neg * integer;
}
}
}
Second solution
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define si(x) scanf("%d",&x)
#define pi(x) printf("%d\n",x)
#define s(x) scanf("%lld",&x)
#define p(x) printf("%lld\n",x)
#define sc(x) scanf("%s",x)
#define pc(x) printf("%s",x)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define inf 1e18
#define prec(x) fixed<<setprecision(15)<<x
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mem(x,y) memset(x,y,sizeof(x))
#define PQG priority_queue< int,std::vector<int>,std::greater<int> >
#define PQL priority_queue< int,std::vector<int>,std::less<int> >
#define PQPL priority_queue<pii ,vectosr< pii >, less< pii > >
#define PQPG priority_queue<pii ,vector< pii >, greater< pii > >
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
#endif
int n; cin>>n;
assert(n>=1 && n<=100000);
string s[n];
for(int i=0;i<n;i++) {
cin>>s[i];
ll x=0;
for(char c:s[i]) {
x=x*10+(ll)(c-'0');
}
assert(x>=1 && x<=inf);
}
int cnt[10];
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;i++) {
int sz=s[i].size();
set<int>ss;
for(int j=0;j<sz;j++) {
ss.insert(s[i][j]-'0');
}
int val=0;
for(int x:ss) val=max(val,cnt[x]);
for(int x:ss) cnt[x]=val+1;
}
int ans=0;
for(int i=0;i<10;i++) {
ans=max(ans,cnt[i]);
}
cout<<ans<<endl;
return 0;
}
0 Comments