#include<bits/stdc++>
using namespace std;
//recursion start block
double e(int x,int n)
{
static int p=1,f=1;.
double r;
if(n==0)
return (1);
else
{
r=e(x,n-1);
p=p*x;
f=f*n;
}
return r+p/f;
}
// recursion function end block
// other than recursion
#include
ReplyDeleteusing namespace std;
int main()
{
string s;
cin>>s;
int n=s.size();
int ans=0;
vector last(256,-1);
int i=0;
for(int j=0;j<n;j++)
{
i=max(i,last[s[j]]+1);
ans=max(ans,j-i+1);
last[s[j]]=j;
}
cout<<ans<<endl;
return 0;
}
This the function code of longest substring which return size.
Deletebool isPalindrome(string s) {
ReplyDeleteint n = s.length();
for(int i = 0; i < n/2; i++) {
if(s[i] != s[n-i-1]) {
return false;
}
}
return true;
}
Count of non-empty substrings is n*(n+1)/2
ReplyDeleteIf we include empty string also as substring, the count becomes n*(n+1)/2 + 1
How does above formula work?
Number of substrings of length one is n (We can choose any of the n characters)
Number of substrings of length two is n-1 (We can choose any of the n-1 pairs formed by adjacent)
Number of substrings of length three is n-2
(We can choose any of the n-2 triplets formed by adjacent)
In general, number of substrings of length k is n-k+1 where 1 <= k <= n
Total number of substrings of all lengths from 1 to n =
n + (n-1) + (n-2) + (n-3) + … 2 + 1
= n * (n + 1)/2
maximum Sub array
ReplyDelete#include
using namespace std;
int main()
{
int n,csum=0;
cin>>n;
int ar[n];
int maxSum=INT_MIN;
for(int i=0;i>ar[i];
}
int sum=0;
for (int i = 0; i < n; i++)
{
sum +=ar[i];
if(sum<0)
sum=0;
maxSum=max(maxSum,sum);
}
cout<<maxSum;
return 0;
}