Join Regular Classroom : Visit ClassroomTech

Longest Unique Substring of a string – Infytq 2019 Solve

/ Miscellaneous / By

Problem: Find the longest substring of unique characters which is case insensitive. Minimum length of the substring should be 3. If the criteria doesn’t match then returns -1.

Input Format: First line contains a single integer n, the number of testcases. Next n line contains n strings as input.

(NOTE: The actual problem didn’t have the number of testcases as input. But for your better convenience we have worked with testcases.)

Sample Input:

3
abcdabc
abababab
abAca

Sample Output: 

abcd
-1
abAc

Explanation: Here in the first example, the longest substring that can be made keeping the criteria, is “abcd” which means the first longest substring made will be taken into consideration.

Here in the second case, the longest unique substring that can be made is “ab” but it doesn’t fulfil the criteria. Hence prints -1.

Lastly, the longest unique substring that can be made is “abAc” since its case insensitive ‘A’ is allowed and will be counted as a unique character.

Solution 1: We strongly recommend you to try the problem first before moving to the solution.

Python

# Solution of longest unique even integer problem in Python 
# www.codewindow.in

def solve(str):
    length=len(str)
    unique=''
    
    for i in range (length):
        substr=str[i]
    
        for j in range (i+1, length):
            substr += str[j]
            sub_len=len(substr)
    
            if sub_len>=3 and len(set(substr))==sub_len:
                if len(unique)<sub_len:
                    unique=substr
    
    if len(unique)==0:
        print("-1")
    else:
        print(unique)

# Driver Code
test_case=int(input());     # Take number of testcases
while(test_case):
    str=input()
    solve(str)
    test_case-=1

C++

#include <bits/stdc++.h>
#define ll long long
#define all(c) (c).begin(), (c).end()
using namespace std;

void solve() {
    string s, temp;
    cin >> s;

    for(int i=0; i<s.length(); ++i) {
        bool ok=1;
        temp=s.substr(0, i);  
        // substr(size_t starting_pos, size_t length_of_substring)
        for(int j=0; j<=i; ++j) {
            if(count(all(temp), temp[i-1])>1) {   
               // Count the frequency of each character we are adding up.
                temp.pop_back();    
               // If frequency of that character is > 1 then pop that character from string
                ok=0;    
               // Turn the boolean into 0. Used for flag.
                break;    
               // Break the entire process
            }
        }
        if(ok==0)    
        // We have reached the maximum limit and we don't want to continue.  
            break;
    }
    
    if(temp.length()<3)
        cout << "-1" << "\n";
    else
        cout << temp << "\n";
}

// Driver Code
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t=1;
	cin >> t;    // Testcases
	
	while(t--)
	    solve();
	
	return 0;
}

Input:

3
abcdabc
abababab
abAca

Output:

abcd
-1
abAc

Follow Us

You Missed