Last Updated: 10 Sep, 2021

Cybersecurity And Password

Hard

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 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 :

Create a variable (say, ‘N’) that will store the length of the string.
Create a variable (say, ‘MISS’) that will store the number of missing conditions present in the password.
Create a variable (say, ‘RES’) that will store the result and initialize it with 0.
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.
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.
Check if ‘N’ is smaller than 6.
- Return the maximum of 6 - ‘N’ and ‘MISS’.
Check if ‘N’ is smaller than equal to 20.
- Return the maximum of ‘RES’ and ‘MISS’.
Create a variable (say, ‘DEL’) that will store the number of deletions and initialize it with ‘N’ - 20.
Update ‘RES’ by subtracting the minimum of ‘ONES’ and ‘DEL’.
Update ‘RES’ by subtracting the minimum of ‘ONES’ and ‘DEL’. (1 deletion case).
Update ‘RES’ by subtracting the minimum of )maximum of (‘DEL’ - ‘ONES’ and 0) and ‘TWOS’ * 2) / 2. ( 2 deletions case).
Update ‘RES’ by subtracting the maximum of (‘DEL’ - ‘ONES’ - ‘TWOS’ * 2 and 0) / 3. ( 3 deletions case).
Finally, return the sum of ‘DEL’ and maximum of ‘RES’ and ‘MISS’.

Solve now