š Day-12 Striverās SDE Sheet | Arrays Part 4 | Count number of subarrays with given xor K , Longest Substring without repeat.


Note : Started my 27-day DSA journey with Striverās SDE Sheet!
I will be journaling every day ā recording what I learn, reflecting on it, and sharing it with my network to help fellow learners and aspiring developers.. Learning through videos, resources, and the internet ā simplifying logic in my own way with real-world connections. Sharing 2 questions daily: brute-force to optimal, clean Java code, time & space complexity, and key patterns.
This blog series is for anyone preparing for coding interviews ā whether youāre a beginner or a revision warrior. Letās grow together! š
Namaste Developers! š
Welcome to Day 12 of my 27-day DSA journey using Striverās SDE Sheet!
1ļøā£ Count number of subarrays with given xor K
šø Problem Statement:
Given an array of integers A and an integer B. Find the total number of subarrays having bitwise XOR of all elements equal to k.
Example 1:
Input Format: A = [4, 2, 2, 6, 4] , k = 6
Result: 4
Explanation: The subarrays having XOR of their elements as 6 are [4, 2], [4, 2, 2, 6, 4], [2, 2, 6], [6]
Example 2:
Input Format: A = [5, 6, 7, 8, 9], k = 5
Result: 2
Explanation: The subarrays having XOR of their elements as 5 are [5] and [5, 6, 7, 8, 9]
š Real World Example
XOR ka matlab hota hai exclusive OR ā jisme bits alag ho tabhi result 1 hota hai.
Input A | Input B | Output |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Think of XOR like this:-
ā Suppose you and your friend both have different ideas, toh combined result exciting hoga (1).
ā But if you both think the same (0,0 or 1,1), toh result boring hoga (0).
(Hinglish : XOR ko aise socho:
Agar tum aur tumhara friend dono ke ideas alag-alag hain, toh jo result aayega wo exciting hoga (1).
Lekin agar dono same soch rahe ho (jaise 0-0 ya 1-1), toh result boring hoga (0).)
š Brute Force Approach ā TLE Risk but Concept Clear
šIdea:
Check every subarray.
Calculate XOR of all elements.
Count if XOR == k.
class Solution {
public long subarrayXor(int arr[], int k) {
int count = 0;
for (int i = 0; i < arr.length; i++) {
int xor = 0;
for (int j = i; j < arr.length; j++) {
xor ^= arr[j];
if (xor == k) count++;
}
}
return count;
}
}
šTime Complexity (TC):
- O(n²) ā because of nested loop
š Space Complexity (SC):
- O(1) ā no extra space used
ā ļø Note:
Brute force TLE de sakta hai jab input bada ho, like
10^5
size array!
š Optimal Approach ā HashMap with XOR Concept
šIntuition:
Letās say we calculate prefix XOR till index i
:
Let
xor
= prefix XOR till indexi
Then, we check:
If(xor ^ k)
already occurred before,
then there exists a subarray whose XOR = k.
XOR property used:
If A ^ B = C, then A = B ^ C and B = A ^ C
So, we use a HashMap to store frequency of prefix XORs.
class Solution {
public long subarrayXor(int arr[], int k) {
Map<Integer, Integer> map = new HashMap<>();
int count = 0;
int xor = 0;
for (int i = 0; i < arr.length; i++) {
xor ^= arr[i];
if (xor == k) count++;
int required = xor ^ k;
count += map.getOrDefault(required, 0);
map.put(xor, map.getOrDefault(xor, 0) + 1);
}
return count;
}
}
ā Step-by-step Dry Run:
Index | Num | xor (prefix XOR) | xor ^ k = needed | Map Lookup | Add to Count | Updated Map | Total Count |
0 | 4 | 0 ^ 4 = 4 | 4 ^ 6 = 2 | ā (not found) | ā | {4: 1} | 0 |
1 | 2 | 4 ^ 2 = 6 | 6 ^ 6 = 0 | ā | ā xor == k | {4:1, 6:1} | 1 |
2 | 2 | 6 ^ 2 = 4 | 4 ^ 6 = 2 | ā | ā | {4:2, 6:1} | 1 |
3 | 6 | 4 ^ 6 = 2 | 2 ^ 6 = 4 | ā found 4 ā map[4]=2 | ā +2 subarrays | {4:2, 6:1, 2:1} | 3 |
4 | 4 | 2 ^ 4 = 6 | 6 ^ 6 = 0 | ā | ā xor == k | {4:2, 6:2, 2:1} | 4 |
ā Final Count = 4
šTime Complexity:
- O(n) ā one traversal
šSpace Complexity:
- O(n) ā for HashMap
š Real World Application
Network Security ā XOR used in encryption (e.g. stream ciphers)
Bit Manipulation Problems ā Used in leetcode, CP (competitive programming)
Debugging ā Finding unique elements, prefix sums with twist
(Tips Hinglish :
āPrefix XORā ka idea samajhna zaroori hai ā har index tak ka XOR calculate karna.
āxor ^ kā = required value jo map mein search karni hai.
HashMap frequency store karne ke kaam aata hai ā bina dikhaye kaam karta hai background mein)
2ļøā£ Longest Substring Without Repeating Characters
šø Problem Statement:
Given a string s
, find the length of the longest substring without duplicate characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 10<sup>4</sup>
s
consists of English letters, digits, symbols and spaces.
šReal World Example
Imagine youāre playing a memory game :
You have to keep selecting different cards (characters),
The moment you pick a duplicate card, your current streak ends.
You start a new streak from the next card.
Aisa hi kuch hum kar rahe hain is problem mein!
š Brute Force Approach
šIdea:
Generate all substrings.
For each substring, check if all characters are unique.
class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLength = 0;
for (int i = 0; i < s.length(); i++) {
Set<Character> set = new HashSet<>();
for (int j = i; j < s.length(); j++) {
if (set.contains(s.charAt(j))) break;
set.add(s.charAt(j));
maxLength = Math.max(maxLength, j - i + 1);
}
}
return maxLength;
}
}
šTime Complexity: O(n²)
šSpace Complexity: O(n)
š Optimal Approach ā Sliding Window + HashSet
šIdeas:
Use two pointers (left and right) to create a window.
Move
right
pointer to include new characters.If duplicate found, move
left
pointer to remove until no duplicates remain.
Set use karenge to track which characters are inside window.
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int left = 0, right = 0, maxLen = 0;
while (right < s.length()) {
char ch = s.charAt(right);
if (!set.contains(ch)) {
set.add(ch);
maxLen = Math.max(maxLen, right - left + 1);
right++;
} else {
set.remove(s.charAt(left));
left++;
}
}
return maxLen;
}
}
šTime Complexity: O(n)
šSpace Complexity: O(n)
š Dry Run ā s = "abcabcbb"
Step | Left | Right | Char | Set Content | maxLen |
1 | 0 | 0 | a | {a} | 1 |
2 | 0 | 1 | b | {a, b} | 2 |
3 | 0 | 2 | c | {a, b, c} | 3 ā |
4 | 0 | 3 | a | Duplicate ā move left | |
5 | 1 | 3 | a | {b, c, a} | 3 |
... | Keep going | ||||
Final | |||||
ā Answer: maxLen = 3 for substring "abc" |
(Hinglish Tips
Set
ko samjho: it stores only unique elements. Duplicate mila toh remove karoleft
se.Sliding window
ka matlab hota hai ek range jise hum dynamically adjust karte hain.Donāt memorize ā understand the logic. Try dry runs manually.)
āļø Final Notes:
If you're just starting your DSA journey like me, don't worry if you donāt get it perfect the first time.
Visualize ā Dry Run ā Optimize.
Stay consistent, and letās crack every problem from brute to optimal! šŖ
š Special Thanks
A heartfelt thank you to Rajvikraaditya Sir for creating and sharing such an incredible DSA resource with the community (takeuforward). Your structured approach has made DSA more accessible and less intimidating for thousands of learners like me.
If this helped you, do share it with your fellow DSA learners.
Comment with your doubts ā Iād love to answer and grow together š±
āļø Payal Kumari š©āš»
My 27-Day DSA Journey with Striverās Sheet! #dsawithpayal
Subscribe to my newsletter
Read articles from Payal Kumari directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by

Payal Kumari
Payal Kumari
I'm a passionate full-stack developer with a strong foundation in the MERN stackābuilding and maintaining scalable web applications using React.js, Node.js, and Next.js. My journey in open source began with Hacktoberfest 2023, where I made four impactful pull requests that sparked a love for collaborative coding, global learning, and open knowledge sharing. Since then, Iāve contributed to and mentored projects in top open source programs like GSSoCā24, SSOCā24, and C4GTā24. As a Google Gen AI Exchange Hackathon ā24 Finalist and Googleās Women Techmakers (WTM) Ambassador, Iāve been privileged to support diverse communities in building meaningful tech solutions. My work as a Top 50 Mentor for GSSoC ā24 reflects my commitment to nurturing new talent in tech. Beyond development, I serve as a Student Career Guide, Profile Building Expert & Evangelist at Topmate.io, where I conduct workshops, guide students through resume building and career strategy, and help mentees navigate open source and tech careers. Recognized among the Top 5% of mentors and featured on āTopmate Discover,ā I take pride in making mentorship accessible and impactful. My technical voice has also been acknowledged by LinkedIn, where Iāve earned the Top Voice badge seven times in domains like web development, programming, and software engineering. In addition, I hold LinkedIn Golden Badges for Research Skills, Interpersonal Skills, Critical Thinking, and Teamworkāsignaling a well-rounded approach to both individual contribution and team collaboration. Graduating with an MCA from Chandigarh University in 2023, Iāve continued to fuel my curiosity by writing technical articles and sharing practical MERN stack insights across platforms. Whether itās building polished UIs, optimizing backend performance, or guiding a mentee through their first pull request, Iām driven by the power of community and continuous learning. Letās connect! I'm open to collaborations, mentorship, or building something impactful together. Reach out to me at kumaripayal7488@gmail.com or visit my profile on Topmate.io.