Cybersecurity And Password

Hard
0/120
Average time to solve is 40m
profile
Contributed by
4 upvotes
Asked in companies
AdobePwC India

Problem statement

Passwords should be easy to remember but difficult to hack or guess. According to Ninja Cyber Security Centre, a password should have a minimum of 6 lengths and a maximum of 20 lengths. It should have at least one lowercase letter, one uppercase letter, and one digit. The most important condition is that the password should not contain any repeating characters of length more than 2.

Given a string ‘STR’ as a password, find the minimum number of changes we need to make to strengthen that password. We can insert a character, delete a character and replace a character from the password at a time.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, representing the number of test cases.

The first line of each test case contains a string ‘STR’, representing the password.
Output Format : 
For each test case, print a single integer, representing the number of changes we need to make.

Output for each test case will be printed in a separate line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= |STR| <= 5000

Where |STR| is the length of the given string ‘STR’.

Time Limit : 1 sec
Sample Input 1 :
2
a
abcdefg
Sample Output 1 :
5
2
Explanation For Sample Input 1 :
For first test case :

Given password : a
We have to do a minimum of 5 changes to the password to make its length 6.
Possible password : aAbBc1
Number of changes done : 5

For second test case :

 Given password : abcdefg
We need one uppercase and one digit to strengthen the password.
Possible password : Abcdef1
Number of changes done : 2
Sample Input 2 :
2
1337C0d
aA1
Sample Output 2 :
0
3
Hint

Greedily check for all the conditions.

Approaches (1)
Greedy Approach

The idea is to check for all the conditions greedily. We need to check whether the password consists of at least one lowercase letter, one uppercase, and one digit and no repeated characters of length more than 2. There are 3 possible combinations, i.e., ‘N’ < 6, ‘N’ <= 20 and ‘N’ > 20.

For ‘N’ < 6 , we can insert the missing conditions.

For ‘N’ <= 20, we can replace the necessary characters.

For ‘N’ > 20, we can do combinations of deletions and replacements.

Example:

bbbbbb: In this, we can delete the last character and do 1 replacement.

bbbbbbb: In this, we can do 2 deletions to save 1 replacement.

bbbbbbbb: In this, we can do 3 deletions to save 1 replacement.

 

Here is the algorithm :
 

  1. Create a variable (say, ‘N’) that will store the length of the string.
  2. Create a variable (say, ‘MISS’) that will store the number of missing conditions present in the password.
  3. Create a variable (say, ‘RES’) that will store the result and initialize it with 0.
  4. Create two variables (say, ‘ONES’ and ‘TWOS’) that will store the combinations that can be substituted with 1 and 2 deletions, respectively, and initialize them with 0.
  5. Run a loop from 2 to ‘N’ (say, iterator ‘i’)
    • Check if ‘STR[i]’ is equal to ‘STR[i - 1]’ and ‘STR[i - 2]’.
    • Create a variable (say, ‘LEN’) that will store the length of the sequence with repeated characters and initialize it with 2.
    • Run a loop ‘i’ is smaller than ‘N’, and ‘STR[i]’ is equal to ‘STR[i - 1]’.
      • Increment ‘LEN’ by 1.
      • Increment ‘i’ by 1.
    • Update ‘RES’ by ‘RES’ + ‘LEN / 3’.
    • Check if ‘LEN % 3’ is equal to 0.
      • Increment ‘ONES’ by 1.
    • Check if ‘LEN % 3’ is equal to 1.
      • Increment ‘TWOS’ by 1.
    • Else, increment ‘i’ by 1.
  6. Check if ‘N’ is smaller than 6.
    • Return the maximum of 6 - ‘N’ and ‘MISS’.
  7. Check if ‘N’ is smaller than equal to 20.
    • Return the maximum of ‘RES’ and ‘MISS’.
  8. Create a variable (say, ‘DEL’) that will store the number of deletions and initialize it with ‘N’ - 20.
  9. Update ‘RES’ by subtracting the minimum of ‘ONES’ and ‘DEL’.
  10. Update ‘RES’ by subtracting the minimum of ‘ONES’ and ‘DEL’.  (1 deletion case).
  11. Update ‘RES’ by subtracting the minimum of )maximum of (‘DEL’ - ‘ONES’ and 0) and ‘TWOS’ * 2) / 2.  ( 2 deletions case).
  12. Update ‘RES’ by subtracting the maximum of (‘DEL’ - ‘ONES’ - ‘TWOS’ * 2  and 0) / 3.  ( 3 deletions case).
  13. Finally, return the sum of ‘DEL’ and maximum of ‘RES’ and ‘MISS’.
Time Complexity

O(N), where ‘N’ is the length of the string.

 

We traverse the string once to check for the conditions. Therefore, the overall time complexity will be O(N).

Space Complexity

O(1)

 

We are not using any extra space. Therefore, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Cybersecurity And Password
Full screen
Console